#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
vector<int> g[500005];
vector<int> rg[500005];
int st[500005];
int dep[500005];
int ddep[500005];
int t;
int ett[1000005];
int rev[1000005];
void dfs(int u, int p = 0, int d = 0){
t++;
ddep[u] = d;
ett[t] = dep[u] = dep[p]+1;
st[u] = t;
rev[t] = u;
for(int v : g[u]){
if(v == p) continue;
dfs(v, u, d+1);
t++;
ett[t] = dep[u];
rev[t] = u;
}
for(int v : rg[u]){
if(v == p) continue;
dfs(v, u, d-1);
t++;
ett[t] = dep[u];
rev[t] = u;
}
}
pair<int, int> sparse[21][1048576];
void build(){
for(int i = 0; i < 1000005; i++) sparse[0][i] = {ett[i], rev[i]};
for(int i = 1; i < 21; i++){
for(int j = 0; j + (1 << i) < 1048576; j++){
sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j+(1<<(i-1))]);
}
}
}
inline pair<int,int> rmq(const int& l, const int& r){
int d = r-l+1;
int lg = 31 - __builtin_clz(d);
return min(sparse[lg][l], sparse[lg][r-(1<<lg)+1]);
}
inline int lca(int u, int v){
if(st[u] > st[v]) swap(u, v);
return rmq(st[u], st[v]).second;
}
inline bool search(int a, int d){
int l = lca(a, d);
int dist = dep[a] + dep[d] - 2*dep[l];
int ddist = ddep[d] - ddep[a];
return dist == ddist;
}
gp_hash_table<int, int> buffer;
const int THRESH = 750;
int qs[500005];
int evp[500005];
int update(int u, int p = 0, int d = 0){
for(int v : rg[u]){
if(v == p) continue;
d += update(v, u, 0);
}
d += evp[u];
qs[u] += d;
for(int v : g[u]){
if(v == p) continue;
update(v, u, d);
}
return d;
}
int count(int d){
if(buffer.size() >= THRESH){
for(auto p : buffer) evp[p.first] += p.second;
update(1);
for(auto p : buffer) evp[p.first] -= p.second;
buffer.clear();
}
int ret = qs[d];
for(auto p : buffer){
if(search(p.first, d)){
ret += p.second;
}
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
k += n-1;
vector<tuple<int,int,int>> cmds;
vector<int> ids(n+1);
for(int i = 1; i <= n; i++){
ids[i] = i;
}
int last = n;
for(int i = 0; i < k; i++){
string cmd;
cin >> cmd;
int a, b, d;
switch(cmd[0]){
case 'S':
cin >> a >> b;
last++;
g[last].push_back(ids[a]);
rg[ids[a]].push_back(last);
g[last].push_back(ids[b]);
rg[ids[b]].push_back(last);
ids[a] = ids[b] = last;
cmds.push_back({0, a, b});
break;
case 'Q':
cin >> a >> d;
cmds.push_back({1, a, d});
break;
case 'C':
cin >> d;
cmds.push_back({2, d, 0});
break;
}
}
dfs(1);
build();
for(int i = 1; i <= n; i++){
ids[i] = i;
buffer[i]++;
}
last = n;
for(int i = 0; i < k; i++){
int a, b, d;
switch(get<0>(cmds[i])){
case 0:
a = get<1>(cmds[i]);
b = get<2>(cmds[i]);
buffer[ids[a]]--;
buffer[ids[b]]--;
last++;
ids[a] = ids[b] = last;
buffer[last] += 2;
break;
case 1:
a = get<1>(cmds[i]);
d = get<2>(cmds[i]);
if(search(ids[a], d)) cout << "yes\n";
else cout << "no\n";
break;
case 2:
d = get<1>(cmds[i]);
cout << count(d) << "\n";
break;
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
195012 KB |
Output is correct |
2 |
Correct |
67 ms |
195800 KB |
Output is correct |
3 |
Correct |
58 ms |
195840 KB |
Output is correct |
4 |
Correct |
64 ms |
195800 KB |
Output is correct |
5 |
Correct |
57 ms |
196008 KB |
Output is correct |
6 |
Correct |
57 ms |
196096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
195012 KB |
Output is correct |
2 |
Correct |
67 ms |
195800 KB |
Output is correct |
3 |
Correct |
58 ms |
195840 KB |
Output is correct |
4 |
Correct |
64 ms |
195800 KB |
Output is correct |
5 |
Correct |
57 ms |
196008 KB |
Output is correct |
6 |
Correct |
57 ms |
196096 KB |
Output is correct |
7 |
Correct |
54 ms |
195016 KB |
Output is correct |
8 |
Correct |
393 ms |
197660 KB |
Output is correct |
9 |
Correct |
248 ms |
198144 KB |
Output is correct |
10 |
Correct |
310 ms |
197604 KB |
Output is correct |
11 |
Correct |
180 ms |
197896 KB |
Output is correct |
12 |
Correct |
187 ms |
198152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
195132 KB |
Output is correct |
2 |
Correct |
116 ms |
234132 KB |
Output is correct |
3 |
Correct |
117 ms |
234112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
195132 KB |
Output is correct |
2 |
Correct |
116 ms |
234132 KB |
Output is correct |
3 |
Correct |
117 ms |
234112 KB |
Output is correct |
4 |
Correct |
58 ms |
195016 KB |
Output is correct |
5 |
Correct |
1481 ms |
231556 KB |
Output is correct |
6 |
Correct |
1684 ms |
231716 KB |
Output is correct |
7 |
Correct |
1714 ms |
231548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
195124 KB |
Output is correct |
2 |
Correct |
144 ms |
232888 KB |
Output is correct |
3 |
Correct |
148 ms |
233088 KB |
Output is correct |
4 |
Correct |
107 ms |
234364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
195124 KB |
Output is correct |
2 |
Correct |
144 ms |
232888 KB |
Output is correct |
3 |
Correct |
148 ms |
233088 KB |
Output is correct |
4 |
Correct |
107 ms |
234364 KB |
Output is correct |
5 |
Correct |
57 ms |
195100 KB |
Output is correct |
6 |
Execution timed out |
3553 ms |
230344 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
194984 KB |
Output is correct |
2 |
Correct |
116 ms |
222596 KB |
Output is correct |
3 |
Correct |
142 ms |
222004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
194984 KB |
Output is correct |
2 |
Correct |
116 ms |
222596 KB |
Output is correct |
3 |
Correct |
142 ms |
222004 KB |
Output is correct |
4 |
Correct |
55 ms |
195044 KB |
Output is correct |
5 |
Correct |
1069 ms |
220012 KB |
Output is correct |
6 |
Correct |
2303 ms |
224128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
195016 KB |
Output is correct |
2 |
Correct |
140 ms |
233088 KB |
Output is correct |
3 |
Correct |
137 ms |
233256 KB |
Output is correct |
4 |
Correct |
115 ms |
234172 KB |
Output is correct |
5 |
Correct |
56 ms |
195020 KB |
Output is correct |
6 |
Correct |
109 ms |
222600 KB |
Output is correct |
7 |
Correct |
131 ms |
221820 KB |
Output is correct |
8 |
Correct |
133 ms |
222404 KB |
Output is correct |
9 |
Correct |
138 ms |
222544 KB |
Output is correct |
10 |
Correct |
131 ms |
227208 KB |
Output is correct |
11 |
Correct |
121 ms |
226432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
195016 KB |
Output is correct |
2 |
Correct |
140 ms |
233088 KB |
Output is correct |
3 |
Correct |
137 ms |
233256 KB |
Output is correct |
4 |
Correct |
115 ms |
234172 KB |
Output is correct |
5 |
Correct |
56 ms |
195020 KB |
Output is correct |
6 |
Correct |
109 ms |
222600 KB |
Output is correct |
7 |
Correct |
131 ms |
221820 KB |
Output is correct |
8 |
Correct |
133 ms |
222404 KB |
Output is correct |
9 |
Correct |
138 ms |
222544 KB |
Output is correct |
10 |
Correct |
131 ms |
227208 KB |
Output is correct |
11 |
Correct |
121 ms |
226432 KB |
Output is correct |
12 |
Correct |
55 ms |
195016 KB |
Output is correct |
13 |
Execution timed out |
3534 ms |
230424 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
195012 KB |
Output is correct |
2 |
Correct |
59 ms |
195808 KB |
Output is correct |
3 |
Correct |
55 ms |
195844 KB |
Output is correct |
4 |
Correct |
60 ms |
195800 KB |
Output is correct |
5 |
Correct |
60 ms |
196096 KB |
Output is correct |
6 |
Correct |
57 ms |
196104 KB |
Output is correct |
7 |
Correct |
50 ms |
195020 KB |
Output is correct |
8 |
Correct |
118 ms |
234368 KB |
Output is correct |
9 |
Correct |
122 ms |
234168 KB |
Output is correct |
10 |
Correct |
52 ms |
194948 KB |
Output is correct |
11 |
Correct |
141 ms |
233084 KB |
Output is correct |
12 |
Correct |
148 ms |
233084 KB |
Output is correct |
13 |
Correct |
109 ms |
234256 KB |
Output is correct |
14 |
Correct |
50 ms |
195024 KB |
Output is correct |
15 |
Correct |
107 ms |
222596 KB |
Output is correct |
16 |
Correct |
137 ms |
221836 KB |
Output is correct |
17 |
Correct |
136 ms |
222348 KB |
Output is correct |
18 |
Correct |
134 ms |
222596 KB |
Output is correct |
19 |
Correct |
125 ms |
227160 KB |
Output is correct |
20 |
Correct |
124 ms |
226292 KB |
Output is correct |
21 |
Correct |
119 ms |
226688 KB |
Output is correct |
22 |
Correct |
125 ms |
227200 KB |
Output is correct |
23 |
Correct |
143 ms |
223604 KB |
Output is correct |
24 |
Correct |
142 ms |
223620 KB |
Output is correct |
25 |
Correct |
141 ms |
228852 KB |
Output is correct |
26 |
Correct |
122 ms |
222588 KB |
Output is correct |
27 |
Correct |
119 ms |
223092 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
54 ms |
195012 KB |
Output is correct |
2 |
Correct |
59 ms |
195808 KB |
Output is correct |
3 |
Correct |
55 ms |
195844 KB |
Output is correct |
4 |
Correct |
60 ms |
195800 KB |
Output is correct |
5 |
Correct |
60 ms |
196096 KB |
Output is correct |
6 |
Correct |
57 ms |
196104 KB |
Output is correct |
7 |
Correct |
50 ms |
195020 KB |
Output is correct |
8 |
Correct |
118 ms |
234368 KB |
Output is correct |
9 |
Correct |
122 ms |
234168 KB |
Output is correct |
10 |
Correct |
52 ms |
194948 KB |
Output is correct |
11 |
Correct |
141 ms |
233084 KB |
Output is correct |
12 |
Correct |
148 ms |
233084 KB |
Output is correct |
13 |
Correct |
109 ms |
234256 KB |
Output is correct |
14 |
Correct |
50 ms |
195024 KB |
Output is correct |
15 |
Correct |
107 ms |
222596 KB |
Output is correct |
16 |
Correct |
137 ms |
221836 KB |
Output is correct |
17 |
Correct |
136 ms |
222348 KB |
Output is correct |
18 |
Correct |
134 ms |
222596 KB |
Output is correct |
19 |
Correct |
125 ms |
227160 KB |
Output is correct |
20 |
Correct |
124 ms |
226292 KB |
Output is correct |
21 |
Correct |
119 ms |
226688 KB |
Output is correct |
22 |
Correct |
125 ms |
227200 KB |
Output is correct |
23 |
Correct |
143 ms |
223604 KB |
Output is correct |
24 |
Correct |
142 ms |
223620 KB |
Output is correct |
25 |
Correct |
141 ms |
228852 KB |
Output is correct |
26 |
Correct |
122 ms |
222588 KB |
Output is correct |
27 |
Correct |
119 ms |
223092 KB |
Output is correct |
28 |
Correct |
61 ms |
195016 KB |
Output is correct |
29 |
Correct |
372 ms |
197592 KB |
Output is correct |
30 |
Correct |
239 ms |
197892 KB |
Output is correct |
31 |
Correct |
283 ms |
197604 KB |
Output is correct |
32 |
Correct |
189 ms |
198156 KB |
Output is correct |
33 |
Correct |
192 ms |
198084 KB |
Output is correct |
34 |
Correct |
56 ms |
195012 KB |
Output is correct |
35 |
Correct |
1475 ms |
231552 KB |
Output is correct |
36 |
Correct |
1699 ms |
231676 KB |
Output is correct |
37 |
Correct |
1688 ms |
231552 KB |
Output is correct |
38 |
Correct |
57 ms |
195020 KB |
Output is correct |
39 |
Execution timed out |
3535 ms |
230524 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |