#include<bits/stdc++.h>
#define MAXN 400007
using namespace std;
struct node{
bool ok;
int l,r;
};
int n,q,a[MAXN],b[MAXN],num;
char type[MAXN];
vector<int> v[MAXN];
int sz[MAXN],heavy[MAXN],head[MAXN];
int pos[MAXN],dep[MAXN],parent[MAXN];
void dfs(int x,int p,int dd){
sz[x]=1; dep[x]=dd; parent[x]=p;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p)continue;
dfs(v[x][i],x,dd+1);
if(sz[v[x][i]]>sz[heavy[x]]){
heavy[x]=v[x][i];
}
sz[x]+=sz[v[x][i]];
}
}
void decompose(int x,int p,int h){
if(x==0)return;
num++; pos[x]=num; head[x]=h;
decompose(heavy[x],x,h);
for(int i=0;i<v[x].size();i++){
if(v[x][i]==p or v[x][i]==heavy[x])continue;
decompose(v[x][i],x,v[x][i]);
}
}
node tree[2][4*MAXN];
node combine(int dir,node fr,node sc){
if(fr.l==-1)return sc;
if(sc.l==-1)return fr;
if(dir==0){
if(fr.ok and sc.ok and fr.r<sc.l){
return {true,fr.l,sc.r};
}else{
return {false,fr.l,sc.r};
}
}else{
if(fr.ok and sc.ok and fr.r>sc.l){
return {true,fr.l,sc.r};
}else{
return {false,fr.l,sc.r};
}
}
}
void update(int dir,int v,int l,int r,int pos,int val){
if(l==r){
tree[dir][v]={true,val,val};
}else{
int tt=(l+r)/2;
if(pos<=tt)update(dir,2*v,l,tt,pos,val);
else update(dir,2*v+1,tt+1,r,pos,val);
tree[dir][v]=combine(dir,tree[dir][2*v],tree[dir][2*v+1]);
}
}
node getval(int dir,int v,int l,int r,int ll,int rr){
if(ll>rr){
if(dir==0)return {true,-1,-1};
else return {true,-1,-1};
}
if(l==ll and r==rr){
return tree[dir][v];
}else{
int tt=(l+r)/2;
return combine( dir, getval(dir,2*v,l,tt,ll,min(tt,rr)) , getval(dir,2*v+1,tt+1,r,max(tt+1,ll),rr) );
}
}
bool query(int a,int b){
node lt={true,-1,-1},rt={true,-1,-1};
while(head[a]!=head[b]){
if(dep[head[a]]>dep[head[b]]){
lt=combine(1,lt,getval(1,1,1,n,pos[a],pos[head[a]]));
a=parent[head[a]];
}else{
rt=combine(0,getval(0,1,1,n,pos[head[b]],pos[b]),rt);
b=parent[head[b]];
}
}
if(dep[a]<dep[b]){
rt=combine(0,getval(0,1,1,n,pos[a]+1,pos[b]),rt);
}else{
lt=combine(1,lt,getval(1,1,1,n,pos[b]+1,pos[a]));
}
swap(lt.l,lt.r);
return combine(0,lt,rt).ok;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n+q-1;i++){
cin>>type[i];
if(type[i]=='S'){
cin>>a[i]>>b[i];
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}else if(type[i]=='Q'){
cin>>a[i]>>b[i];
}else{
cin>>a[i];
}
}
dfs(1,0,1);
decompose(1,0,1);
num=0;
for(int i=1;i<=n+q-1;i++){
if(type[i]=='S'){
num++;
if(dep[a[i]]>dep[b[i]])swap(a[i],b[i]);
update(0,1,1,n,pos[b[i]],num);
update(1,1,1,n,pos[b[i]],num);
}else if(type[i]=='Q'){
if(query(b[i],a[i])){
cout<<"yes\n";
}else{
cout<<"no\n";
}
}else{
cout<<0<<"\n";
}
}
return 0;
}
Compilation message
servers.cpp: In function 'void dfs(int, int, int)':
servers.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
servers.cpp: In function 'void decompose(int, int, int)':
servers.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
11448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
11448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
12048 KB |
Output is correct |
| 2 |
Correct |
284 ms |
26692 KB |
Output is correct |
| 3 |
Correct |
285 ms |
26812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
12048 KB |
Output is correct |
| 2 |
Correct |
284 ms |
26692 KB |
Output is correct |
| 3 |
Correct |
285 ms |
26812 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
11612 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
12064 KB |
Output is correct |
| 2 |
Correct |
267 ms |
36164 KB |
Output is correct |
| 3 |
Correct |
261 ms |
36172 KB |
Output is correct |
| 4 |
Correct |
213 ms |
36184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
12064 KB |
Output is correct |
| 2 |
Correct |
267 ms |
36164 KB |
Output is correct |
| 3 |
Correct |
261 ms |
36172 KB |
Output is correct |
| 4 |
Correct |
213 ms |
36184 KB |
Output is correct |
| 5 |
Incorrect |
49 ms |
11512 KB |
Extra information in the output file |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
11636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
11636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
11960 KB |
Output is correct |
| 2 |
Correct |
294 ms |
36172 KB |
Output is correct |
| 3 |
Correct |
264 ms |
36216 KB |
Output is correct |
| 4 |
Correct |
201 ms |
36208 KB |
Output is correct |
| 5 |
Incorrect |
88 ms |
11612 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
11960 KB |
Output is correct |
| 2 |
Correct |
294 ms |
36172 KB |
Output is correct |
| 3 |
Correct |
264 ms |
36216 KB |
Output is correct |
| 4 |
Correct |
201 ms |
36208 KB |
Output is correct |
| 5 |
Incorrect |
88 ms |
11612 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
11568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
11568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
