#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr int MAXN = 120120, LOGN = 20;
vector<pair<int, int>> adj[MAXN];
struct Seg{
vector<int> tree;
int sz;
void init(int n){
sz = n+1;
tree.resize(sz*2);
}
void update(int p, int x){
for (tree[p+=sz]+=x;p>1;p>>=1) tree[p>>1] = tree[p] + tree[p^1];
}
int query(int l){
int r = sz, ret = 0;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret += tree[l++];
if (r&1) ret += tree[--r];
}
return ret;
}
};
struct Cent{
int sz[MAXN], cpa[MAXN], cdep[MAXN];
bool visited[MAXN];
int subt[LOGN][MAXN], idx[LOGN][MAXN], pt[MAXN];
bool gou[LOGN][MAXN], god[LOGN][MAXN];
Seg tree[MAXN];
int getsz(int s, int pa = -1){
sz[s] = 1;
for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
return sz[s];
}
int getcent(int s, int cap, int pa = -1){
for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2 > cap) return getcent(v, cap, s);
return s;
}
void dfs1(int s, int root, int pa, int dep){
subt[dep][s] = root;
for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) dfs1(v, root, s, dep);
}
void dnc(int s, int dep = 1, int pa = -1){
getsz(s);
int c = getcent(s, sz[s]);
for (auto &[v, w]:adj[c]) if (!visited[v]) dfs1(v, v, c, dep); ///init subt
cdep[c] = dep, cpa[c] = pa;
tree[c].init(adj[c].size());
visited[c] = 1;
gou[dep][c] = god[dep][c] = 1;
for (auto &[v, w]:adj[c]) if (!visited[v]){
dnc(v, dep+1, c);
}
}
void dfs2(int s, int dep, int pa, int cst){
gou[dep][s] = 1;
for (auto &[v, w]:adj[s]) if (cdep[v]>dep && v!=pa && w!=-1 && w<cst) dfs2(v, dep, s, w);
}
void update(int v, int w, int cst){
if (cdep[v]>cdep[w]) swap(v, w);
idx[cdep[v]][w] = ++pt[v];
tree[v].update(idx[cdep[v]][w], 1);
dfs2(w, cdep[v], v, cst);
god[cdep[v]][w] = 1;
for (int s=cpa[v];s!=-1;s=cpa[s]){
if (god[cdep[s]][v]) god[cdep[s]][w] = 1;
else if (god[cdep[s]][w]) god[cdep[s]][v] = 1;
int pos = idx[cdep[s]][subt[cdep[s]][v]];
tree[s].update(pos, 1);
}
}
bool query(int s, int e){
if (s==e) return 1;
int u = s, v = e;
if (cdep[u]>cdep[v]) swap(u, v);
while(cdep[u]!=cdep[v]) v = cpa[v];
while(u!=v) u = cpa[u], v = cpa[v];
assert(u!=-1);
int s1 = subt[cdep[u]][s], e1 = subt[cdep[u]][e];
return gou[cdep[u]][s] && god[cdep[u]][e] && idx[cdep[u]][s1] < idx[cdep[u]][e1];
}
int count(int s){
int ret = tree[s].query(0)+1;
//if (s==2) printf("%d %d: %d\n",s, cdep[s], ret);
for (int c=cpa[s];c!=-1;c=cpa[c]) if (gou[cdep[c]][s]){
int tmp = subt[cdep[c]][s];
int pos = idx[cdep[c]][tmp];
ret += tree[c].query(pos+1)+1;
//if (s==2) printf("%d %d: %d\n", c, cdep[c], ret);
}
return ret;
}
}cent;
struct Query{
char op;
int x, y;
Query(){}
Query(char _op, int _x, int _y): op(_op), x(_x), y(_y) {}
}Q[MAXN*2];
int main(){
int n, q;
scanf("%d %d", &n, &q);
for (int i=1,cnt=1;i<=n+q-1;i++){
char op;
int x, y = -1;
scanf(" %c %d", &op, &x);
if (op!='C') scanf("%d", &y);
if (op=='S'){
adj[x].emplace_back(y, cnt);
adj[y].emplace_back(x, cnt);
cnt++;
}
Q[i] = Query(op, x, y);
}
cent.dnc(1);
for (int i=1,cnt=1;i<=n+q-1;i++){
if (Q[i].op=='S'){
cent.update(Q[i].x, Q[i].y, cnt);
cnt++;
}
else if (Q[i].op=='Q'){
if (cent.query(Q[i].y, Q[i].x)) printf("yes\n");
else printf("no\n");
}
else{
printf("%d\n", cent.count(Q[i].x));
}
}
return 0;
}
Compilation message
servers.cpp: In member function 'int Cent::getsz(int, int)':
servers.cpp:38:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) sz[s] += getsz(v, s);
| ^
servers.cpp: In member function 'int Cent::getcent(int, int, int)':
servers.cpp:42:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa && sz[v]*2 > cap) return getcent(v, cap, s);
| ^
servers.cpp: In member function 'void Cent::dfs1(int, int, int, int)':
servers.cpp:48:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | for (auto &[v, w]:adj[s]) if (!visited[v] && v!=pa) dfs1(v, root, s, dep);
| ^
servers.cpp: In member function 'void Cent::dnc(int, int, int)':
servers.cpp:55:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for (auto &[v, w]:adj[c]) if (!visited[v]) dfs1(v, v, c, dep); ///init subt
| ^
servers.cpp:61:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for (auto &[v, w]:adj[c]) if (!visited[v]){
| ^
servers.cpp: In member function 'void Cent::dfs2(int, int, int, int)':
servers.cpp:68:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for (auto &[v, w]:adj[s]) if (cdep[v]>dep && v!=pa && w!=-1 && w<cst) dfs2(v, dep, s, w);
| ^
servers.cpp: In function 'int main()':
servers.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
servers.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | scanf(" %c %d", &op, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~
servers.cpp:127:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | if (op!='C') scanf("%d", &y);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
9540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
9540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
9576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
9576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
9572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
9572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
9632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
9632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
9664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
9664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
9560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
