#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 rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3D2ZDxo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
template<class E>
struct treelca{
int n;
int timer=0;
vec(vec(E)) adj;
vi tin,tout,tour,tourid;
vi segtree;
vi depth;
treelca(int m,int root,vec(vec(E)) neadj){
init(m,root,neadj);
}
void init(int m,int root,vec(vec(E)) neadj){
n=m;
tin.clear();
tout.clear();
tour.clear();
tourid.clear();
depth.clear();
tin.resize(n,0);
tout.resize(n,0);
tourid.resize(n,0);
depth.resize(n,0);
adj=neadj;
dfs(root,-1);
segtree.resize(4*sz(tour));
build(1,0,sz(tour)-1);
}
void dfs(int v,int par){
tour.pb(v);
tourid[v]=sz(tour)-1;
tin[v]=timer++;
for(auto e:adj[v]){
int u=e.to;
if(u==par) continue;
depth[u]=depth[v]+1;
dfs(u,v);
tour.pb(v);
}
tout[v]=timer++;
}
void build(int node,int l,int r){
if(l==r){
segtree[node]=tour[l];
}else{
int m=(l+r)>>1;
build(node*2,l,m);
build(node*2+1,m+1,r);
segtree[node]=(tin[segtree[node*2]]<tin[segtree[node*2+1]]?segtree[node*2]:segtree[node*2+1]);
}
}
int query(int node,int l,int r,int _l,int _r){
if(l>_r or r<_l) return -1;
if(l>=_l and r<=_r) return segtree[node];
int m=(l+r)>>1;
int vl=query(node*2,l,m,_l,_r);
int vr=query(node*2+1,m+1,r,_l,_r);
if(min(vl,vr)==-1) return max(vl,vr);
return (tin[vl]<tin[vr]?vl:vr);
}
int ancestor(int from,int to){
int tinfrom=tin[from],tinto=tin[to];
if(tinfrom>tinto) swap(tinfrom,tinto);
return query(1,0,sz(tour)-1,tinfrom,tinto);
}
int dist(int u,int v){
return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
}
};
struct E{
int to,w;
E(int _to=0,int _w=0):
to(_to),w(_w){}
};
const int inf=1e9;
signed main(){
_3D2ZDxo;
int n,q;
cin>>n>>q;
assert(n<=4000);
q+=n-1;
vec(vec(E)) adj(n);
vec(vec(pii)) qry(n);
vi pns(q,-1);
rep(i,q){
char ch;
cin>>ch;
if(ch=='S'){
int u,v;
cin>>u>>v;
u-=1,v-=1;
adj[u].pb(E(v,i));
adj[v].pb(E(u,i));
}else if(ch=='Q'){
int u,v;
cin>>u>>v;
u-=1,v-=1;
qry[v].pb({u,i});
}else{
int v;
cin>>v;
v-=1;
pns[i]=inf;
}
}
vi leb(n); // last node where increasing seq broke
vi bel(n); // last node where decreasing seq broke
vi par(n);
vi par_wit(n);
auto dfs=[&](auto self,int v,int _lst)->void{
for(auto [u,w]:adj[v]){
if(u==par[v]) continue;
if(_lst>=w){
leb[u]=v;
}else{
leb[u]=leb[v];
}
if(_lst<=w){
bel[u]=v;
}else{
bel[u]=bel[v];
}
par[u]=v;
par_wit[u]=w;
self(self,u,w);
}
};
dfs(dfs,0,0);
vec(vi) afup(20,vi(n)); // affine up
afup[0]=par;
rng(j,1,20){
rep(v,n){
int up=afup[j-1][v];
afup[j][v]=afup[j-1][up];
}
}
treelca<E> lca(n,0,adj);
auto move_down=[&](int v,int up)->int{
int dist=lca.dist(v,up)-1;
per(j,20){
if(dist>>j&1){
v=afup[j][v];
}
}
return v;
};
rep(v,n){
for(auto p:qry[v]){
int u=p.fi;
int j=p.se;
bool pok=0;
if(u==v){
pok=1;
}else{
int up=lca.ancestor(u,v);
if(up==v){
if(lca.depth[leb[u]]<=up){
pok=par_wit[u]<=j;
}
}else if(up==u){
// if(v==4) print(move_down(v,u),bel[u]);
if(lca.depth[bel[v]]<=up){
pok=par_wit[move_down(v,u)]<=j;
}
}else{
if(lca.depth[leb[u]]<=up and lca.depth[bel[v]]<=up){
int lov=move_down(v,up);
int lou=move_down(u,up);
pok=par_wit[lov]<=par_wit[lou] and par_wit[u]<=j;
}
}
}
pns[j]=pok;
}
}
// rep(s,n){
// vi usd(n,inf);
// usd[s]=-1;
// queue<int> que;
// que.push(s);
// while(sz(que)){
// int v=que.front();
// que.pop();
// for(auto [to,w]:adj[v]){
// if(usd[to]==inf and w>usd[v]){
// usd[to]=w;
// que.push(to);
// }
// }
// }
// for(auto p:qry[s]){
// pns[p.se]=(usd[p.fi]<=p.se);
// }
// }
rep(i,q){
if(pns[i]==-1) continue;
if(pns[i]!=inf){
cout<<(pns[i]?"yes":"no")<<"\n";
}else{
cout<<"0\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
2612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
2612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
2716 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
2716 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2620 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2620 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
2732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
2732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
2644 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
2644 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
2728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
2728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
