#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 2e5;
vector<pii>adj[MAXN];
int dep[MAXN],val[MAXN],par[18][MAXN],dd[MAXN],add,n,k;
bool ic[18][MAXN],dc[18][MAXN]; //increaisng path and decreasing path
char c[250000];
int a[250000],d[250000];
void dfs(int v,int u){
if(v<=n && sz(adj[v])==1)adj[v].pb({++add,0});
if(v<=n){
dd[v] = adj[v][0].fi == u?adj[v][1].fi : adj[v][0].fi;
par[0][dd[v]] = v;
for(int i=1;i<=17;i++)par[i][dd[v]] = par[i-1][par[i-1][dd[v]]];
}
for(int i=1;i<=17;i++)par[i][v] = par[i-1][par[i-1][v]];
ic[0][v] = dc[0][v] = 1;
for(int i=1;i<=17;i++){
int x = par[i-1][dd[v]];
int y = par[i-1][v];
if(val[y] < val[x] && dc[i-1][v])dc[i][v] = 1;
if(val[y] > val[x] && ic[i-1][v])ic[i][v] = 1;
}
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];
}
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
cin>>n>>k;
add = n;
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<<42<<'\n';
continue;
}
else{
int v = a[i];
int u = d[i];
if(find(v) != find(u)){
cout<<"no"<<'\n';
continue;
}
bool ok =1;
int last0 = 1e9,last1 = -1e9;
int m = lca(v,u);
if(v!=m){
int x = dd[v];
int y = v;
int d = dep[v]-dep[m];
for(int i=0;i<=17 && d;i++){
if(d&1){
//cout<<i<<" "<<y<<" "<<dc[i][y]<<'\n';
if(!dc[i][y])ok = 0;
x = par[i][x];
y = par[i][y];
//cout<<y<<" "<<x<<" "<<val[y]<<" "<<val[x]<<'\n';
if(y!=m && val[y] > val[x])ok = 0;
}
d/=2;
}
last0 = val[x];
}
if(u!=m){
int x = dd[u];
int y = u;
int d = dep[u]-dep[m];
for(int i=0;i<=17 && d;i++){
if(d&1){
if(!ic[i][y])ok = 0;
x = par[i][x];
y = par[i][y];
if(y!=m && val[y] < val[x])ok = 0;
}
d/=2;
}
last1 = val[x];
}
if(last0 < last1)ok = 0;
if(ok)cout<<"yes"<<'\n';
else cout<<"no"<<'\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
6604 KB |
Output is correct |
| 2 |
Runtime error |
137 ms |
61500 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
6604 KB |
Output is correct |
| 2 |
Runtime error |
137 ms |
61500 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
6568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
6568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
