#include <bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define NO "no"
#define YES "yes"
using namespace std;
const int mxn = 3e5+1 , lg =20 ;
vector<pii> adj[mxn] ;
int tim = 0 ;
vector<int> in(mxn) , out(mxn) , lvl(mxn,-1) , le(mxn,-1) ;
vector<vector<int>> anc(lg,vector<int>(mxn,-1)) , inc(lg,vector<int>(mxn,-1)) , decr(lg,vector<int>(mxn,-1)) ;
int find(int a , int dis){
for(int i=0;i<lg;i++){
if((1<<i)&dis){
a=anc[i][a];
if(a==-1) break ;
}
}
return a ;
}
void dfs(int a ,int p,int l,int lastedge){
in[a]=++tim ;
lvl[a]=l;
anc[0][a]=p;
le[a]=lastedge ;
for(int i=1;i<lg;i++){
if(anc[i-1][a]==-1) continue ;
anc[i][a]=anc[i-1][anc[i-1][a]] ;
}
inc[0][a]=decr[0][a]=lastedge ;
for(int i=1;i<lg;i++){
int na = find(a,(1<<(i-1)-1)) ;
int nb = find(a,(1<<(i-1))) ;
if(na==-1) continue ;
if(nb==-1) continue ;
if((le[nb]==-1||le[na]<le[nb])&&inc[i-1][a]!=-1&&inc[i-1][nb]!=-1) inc[i][a]=inc[i-1][nb];
else inc[i][a]=-1 ;
}
for(int i=1;i<lg;i++){
int na = find(a,(1<<(i-1))-1) ;
int nb = find(a,(1<<(i-1))) ;
if(na==-1) continue ;
if(nb==-1) continue ;
if((le[nb]==-1||le[na]>le[nb])&&decr[i-1][a]!=-1&&decr[i-1][nb]!=-1) decr[i][a]=decr[i-1][a];
else decr[i][a]=-1 ;
}
for(pii x : adj[a]){
if(x.F==p) continue ;
dfs(x.F,a,l+1,x.S);
}
out[a]=++tim;
}
int lca(int a, int b){
if(in[a]<=out[b]&&out[b]<=out[a]) return a ;
if(in[b]<=out[a]&&out[a]<=out[b]) return b ;
for(int i=lg-1;i>-1;i--){
if(anc[i][a]||in[anc[i][a]]<=in[b]&&out[b]<=out[anc[i][a]]) continue;
a =anc[i][a] ;
}
return anc[0][a] ;
}
int is_inc(int a, int lvl){
int ans = 0 ;
for(int i=0;i<lg;i++){
if((1<<i)&lvl){
if(inc[i][a]==-1) return -1 ;
int ba = a ;
a=anc[i][a] ;
if(ans>le[a]) return -1 ;
ans=le[find(ba,(1<<i)-1)];
}
}
return ans ;
}
int is_decr(int a, int lvl){
int ans = 1e9;
int mn = 0 ;
if(lvl!=0) mn=le[a] ;
/* cout << a << " : {" ;
cout << endl ;
for(int i=0;i<lg;i++){
cout << i << " " << decr[i][a] << endl ;
}
cout << "}" ;
cout << lvl << "x"; */
for(int i=0;i<lg;i++){
if((1<<i)&lvl){
if(decr[i][a]==-1)
// cout << "deed" << a << endl ;
// cout<< endl << a << " " << "deded" << decr[i-1][a] << endl ;
return -1 ;
int ba = a ;
a=anc[i][a] ;
if(ans<le[a]){
return -1 ;
}
ans=le[find(ba,(1<<i)-1)];
}
}
// cout <<"answer " << ans << endl ;
return mn ;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n ,q ;
cin>>n>>q ;
int k = n-1+q ;
vector<int> u , v ,t ;
int tim = 0 ;
while(k--){
++tim;
char x ;
cin>>x ;
int a,b ;
cin>>a>>b ;
if(x=='S'){
adj[a].push_back(mp(b,tim));
adj[b].push_back(mp(a,tim)) ;
}
else{
u.push_back(a) ;
v.push_back(b) ;
t.push_back(tim) ;
}
}
dfs(1,-1,0,-1) ;
for(int i=0;i<u.size();i++){
int a = u[i],b = v[i],ti =t[i] ;
int lc = lca(a,b) ;
int pathb = is_inc(b,lvl[b]-lvl[lc]);
int patha=is_decr(a,lvl[a]-lvl[lc]) ;
//cout << a << " " << b << endl ;
//cout <<patha << " " << pathb<< " " << lc << endl ;
if(lc==a){
if(pathb!=-1&&pathb<ti){
cout << YES ;
}
else cout << NO ;
}
else if(lc==b){
if(patha!=-1&&patha<ti) cout << YES ;
else cout << NO ;
}
else{
if(patha==-1||pathb==-1) cout << NO ;
else if(le[find(a,lvl[a]-lvl[lc]-1)]>le[find(b,lvl[b]-lvl[lc]-1)]) cout << YES ;
else if(max(patha,pathb)<ti)cout << NO ;
else cout << YES ;
}
cout << '\n' ;
}
return 0 ;
}
Compilation message
servers.cpp: In function 'void dfs(int, int, int, int)':
servers.cpp:34:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
34 | int na = find(a,(1<<(i-1)-1)) ;
| ~~~~~^~
servers.cpp: In function 'int lca(int, int)':
servers.cpp:59:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
59 | if(anc[i][a]||in[anc[i][a]]<=in[b]&&out[b]<=out[anc[i][a]]) continue;
servers.cpp: In function 'int main()':
servers.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int i=0;i<u.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
85628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
85628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
85576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
85576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
85680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
85680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
85700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
85700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
85740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
85740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
85688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
85688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
