#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
char c[MAXN];
int a[MAXN],d[MAXN],dep[MAXN],val[MAXN],par[18][MAXN];
bool ic[18][MAXN],dc[18][MAXN]; //increaisng path and decreasing path
/*
void dfs(int v,int u){
if(par[0][v]){
ic[0][v] = dc[0][v] = 1;
int last = val[v];
for(int i=1;i<=17;i++){
int mid = par[i-1][v];
par[i][v] = par[i-1][mid];
if(val[mid]){
if(ic[i-1][v] && ic[i-1][mid] && val[mid] > last)ic[i][v] = 1;
if(dc[i-1][v] && dc[i-1][mid] && val[mid] < last)dc[i][v] = 1;
}
last = val[mid];
}
}
for(pii z:adj[v]){
int x = z.fi;
int w = z.se;
if(x == u)continue;
val[x] = w;
dep[x] = dep[v]+1;
par[0][x] = v;
dfs(x,v);
}
}
int lca(int v,int u){
if(dep[v] < dep[u])swap(v,u);
int d = dep[v] - dep[u];
for(int i=0;i<=17;i++){
if(d&(1<<i))v = par[i][v];
}
if(v==u)return v;
for(int i=17;i>=0;i--){
if(par[i][v] != par[i][u]){
v = par[i][v];
u = par[i][u];
}
}
return par[0][v];
}*/
void dfs(int v,int u){
for(pii z:adj[v]){
int x = z.fi;
int w = z.se;
if(x == u)continue;
val[x] = w;
par[0][x] = v;
dep[x] = dep[v]+1;
for(int i=1;i<=17;i++){
par[i][x] = par[i-1][par[i-1][x]];
}
dfs(x,v);
}
}
int lca(int v,int u){
if(dep[v] > dep[u])swap(u,v);
int dist = dep[u]-dep[v];
for(int i=0;dist;i++,dist>>=1){
if(dist&1)u = par[i][u];
}
if(u == v)return u;
for(int i=17;i>=0;i--){
if(par[i][v] != par[i][u]){
u = par[i][u];
v = par[i][v];
}
}
return par[0][v];
}
int p[MAXN];
int find(int x){
if(x==p[x])return x;
else return p[x] = find(p[x]);
}
bool unite(int a,int b){
a = find(a);
b = find(b);
if(a==b)return 0;
p[a] = b;
return 1;
}
int main()
{
owo
int n,k;
cin>>n>>k;
int cnt = 0;
for(int i=1;i<=n;i++)p[i] = i;
for(int i=0;i<n+k-1;i++){
cin>>c[i]>>a[i];
if(c[i]!='C')cin>>d[i];
if(c[i] == 'S'){
adj[a[i]].pb({d[i],++cnt});
adj[d[i]].pb({a[i],cnt});
}
}
dfs(1,0);
for(int i=0;i<n+k-1;i++){
if(c[i] == 'S')unite(a[i],d[i]);
else if(c[i]=='C')cout<<1<<'\n';
else{
int v = a[i];
int u = d[i];
if(find(v) != find(u)){
cout<<"no"<<'\n';
continue;
}
int m = lca(v,u);
/*
int d = dep[v] - dep[m]-1;
bool ok = 1;
int last = 1e9;
for(int i=0;i<=17 && d>=0;i++){
if(d&1){
if(!dc[i][v] || last < val[v])ok = 0;
v = par[i][v];
last = val[v];
}
d/=2;
}
if(v!=m && last < val[v])ok = 0;
//v->lca is decreasing
d = dep[u] - dep[m]-1;
last = 0;
for(int i=0;i<=17 && d>=0;i++){
if(d&1){
//cout<<i<<" "<<u<<" "<<ic[i][u]<<" "<<last<<" "<<val[u]<<'\n';
if(!ic[i][u] || last > val[u])ok = 0;
u = par[i][u];
last = val[u];
}
d/=2;
}
if(u!=m && last > val[u])ok = 0;
if(v!=m && u!=m && val[v] < val[u])ok = 0;
//u->lca is increasing
*/
bool ok = 1;
int last = 1e9;
if(v!=m){
while(par[0][v]!=m){
if(last < val[v])ok = 0;
last = val[v];
v = par[0][v];
}
}
if(last < val[v])ok = 0;
if(u!=m){
last = 0;
while(par[0][u]!=m){
if(last > val[u])ok = 0;
last = val[u];
u = par[0][u];
}
}
if(last > val[u])ok = 0;
if(v!=m && u!=m && val[v] < val[u])ok =0;
if(ok)cout<<"yes"<<'\n';
else cout<<"no"<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
6500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
6500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
6524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
6524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
6464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
6464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
6532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
6532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
6480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
