Submission #7550128
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
# define REP(i,n) for (int i=0;i<(n);++i)
# define PER(i,n) for (int i=(N-1);i>=0;--i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ll;
typedef pair<double,double> P_dd;
const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
struct edge {int to , cost;};
typedef vector<vector<edge>> wgraph; // cost, to
void addM(long long &a, long long b) {
a += b;
if (a >= MOD) a -= MOD;
}
void mulM(long long &a, long long b) {
a = ((a%MOD)*(b%MOD))%MOD ;
}
template<class T>
vector<T> make_vec(size_t a){
return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
for(auto &e:t) fill_v(e,v);
}
vector<ll> dijkstra(wgraph G,int s){
priority_queue<P_ll, vector<P_ll>, greater<P_ll>> que;
vector<ll> dist(G.size(),longinf);
dist[s] = 0;
que.push({0LL, s});
while(!que.empty()){
P_ll p = que.top();que.pop();
ll v = p.second,d = p.first;
if(dist[v] < d) continue;
for(auto e : G[v]){
if(dist[e.to] > dist[v] + e.cost){
dist[e.to] = dist[v] + e.cost;
que.push({dist[e.to], e.to});
}
}
}
return dist;
}
struct DoublingLowestCommonAncestor {
const int LOG;
vector< int > dep;
const wgraph &g;
vector< vector< int > > table;
DoublingLowestCommonAncestor(const wgraph &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
table.assign(LOG, vector< int >(g.size(), -1));
}
void dfs(int idx, int par, int d) {
table[0][idx] = par;
dep[idx] = d;
for(auto&& to : g[idx]) {
if(to.to != par) dfs(to.to, idx, d + 1);
}
}
void build() {
dfs(0, -1, 0);
for(int k = 0; k + 1 < LOG; k++) {
for(int i = 0; i < table[k].size(); i++) {
if(table[k][i] == -1) table[k + 1][i] = -1;
else table[k + 1][i] = table[k][table[k][i]];
}
}
}
int query(int u, int v) {
if(dep[u] > dep[v]) swap(u, v);
for(int i = LOG - 1; i >= 0; i--) {
if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
}
if(u == v) return u;
for(int i = LOG - 1; i >= 0; i--) {
if(table[i][u] != table[i][v]) {
u = table[i][u];
v = table[i][v];
}
}
return table[0][u];
}
};
int main() {
int N;
cin >> N;
wgraph w(N);
REP(i, N - 1){
int x, y;
cin >> x >> y;
w[x - 1].push_back({y - 1, 1});
w[y - 1].push_back({x - 1, 1});
}
auto dist = dijkstra(w, 0);
int Q;
cin >> Q;
vector<P_ll> q(Q);
REP(i, Q){
cin >> q[i].first >> q[i].second;
q[i].first--;
q[i].second--;
}
DoublingLowestCommonAncestor lca(w);
lca.build();
REP(i, Q){
int a = lca.query(q[i].first, q[i].second);
cout << dist[q[i].first] + dist[q[i].second] - 2 * dist[a] + 1 << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
azz |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
4003 Byte |
Status |
AC |
Exec Time |
387 ms |
Memory |
19160 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
1 ms |
256 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
81 ms |
17240 KB |
subtask1_02.txt |
AC |
82 ms |
17240 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
384 KB |
subtask1_06.txt |
AC |
2 ms |
384 KB |
subtask1_07.txt |
AC |
109 ms |
14740 KB |
subtask1_08.txt |
AC |
108 ms |
14540 KB |
subtask1_09.txt |
AC |
109 ms |
14552 KB |
subtask1_10.txt |
AC |
108 ms |
14552 KB |
subtask1_11.txt |
AC |
109 ms |
14552 KB |
subtask1_12.txt |
AC |
107 ms |
14552 KB |
subtask2_01.txt |
AC |
306 ms |
19160 KB |
subtask2_02.txt |
AC |
292 ms |
19032 KB |
subtask2_03.txt |
AC |
190 ms |
2048 KB |
subtask2_04.txt |
AC |
200 ms |
2048 KB |
subtask2_05.txt |
AC |
213 ms |
2304 KB |
subtask2_06.txt |
AC |
218 ms |
2304 KB |
subtask2_07.txt |
AC |
374 ms |
16408 KB |
subtask2_08.txt |
AC |
377 ms |
16332 KB |
subtask2_09.txt |
AC |
386 ms |
16344 KB |
subtask2_10.txt |
AC |
387 ms |
16344 KB |
subtask2_11.txt |
AC |
387 ms |
16344 KB |
subtask2_12.txt |
AC |
387 ms |
16344 KB |