#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 12e4 + 23;
const int LOG = 17;
const ll inf = 1e18;
#define F first
#define S second
#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define lc (v<<1)
#define rc ((v<<1)|1)
struct query {
char c;
int a,b;
int time;
query(char C,int A,int B,int TIME) {
c= C;
a= A;
b= B;
time = TIME;
}
};
int n,m;
vector<pii> G[N];
vector<query> quer;
int up[LOG][N],mx[LOG][N],mn[LOG][N];
bool is[LOG][N],si[LOG][N];
int val[N];
int h[N];
void dfsset(int v,int p = -1,int wp=0){
//if(p != -1) remove(all(G[v]),make_pair(p,wp));
up[0][v] = (p == -1? v: p);
mx[0][v] = mn[0][v] = wp;
is[0][v] = si[0][v] = true;
for(int i = 1; i < LOG; i ++) {
up[i][v] = up[i-1][up[i-1][v]];
mx[i][v] = max(mx[i-1][v],mx[i-1][up[i-1][v]]);
mn[i][v] = min(mn[i-1][v],mn[i-1][up[i-1][v]]);
is[i][v] = is[i-1][v] && (val[up[i-1][v]] <= mn[i-1][v]) && is[i-1][up[i-1][v]];
si[i][v] = si[i-1][v] && (val[up[i-1][v]] >= mx[i-1][v]) && si[i-1][up[i-1][v]];
}
val[v] = wp;
for(auto [u,w] : G[v]) if(u != p) {
h[u] = h[v] + 1;
dfsset(u,v,w);
}
}
int timer= 1;
int gmx(int v,int k) {
int ans=0;
for(int i =0; i < LOG; i ++)
if((k>>i)&1)
ans= max(ans,mx[i][v]),v= up[i][v];
return ans;
}
int gp(int v,int k) {
for(int i = 0 ; i< LOG; i++)
if((k>>i)&1)
v = up[i][v];
return v;
}
int lca(int v,int u) {
if(h[v]< h[u]) swap(v,u);
v = gp(v,h[v] -h[u]);
if(v == u) return v;
for(int i = LOG-1;i >= 0 ; i --)
if(up[i][v] != up[i][u])
v = up[i][v],u = up[i][u];
return up[0][v];
}
bool os(int v,int k) {
bool ans =true;
for(int i = 0 ; i< LOG; i++)
if((k>>i)&1)
ans &= is[i][v]&& val[v] >= val[up[0][v]],v = up[i][v];
return ans;
}
bool so(int v,int k) {
bool ans =true;
for(int i = 0 ; i< LOG; i++)
if((k>>i)&1)
ans &= si[i][v]&&val[v] <= val[up[0][v]],v = up[i][v];
return ans;
}
bool ok(int a,int b) {
// a->b
if(a == b) return true;
int l = lca(a,b);
int mx = max(gmx(a,h[a]-h[l]), gmx(b,h[b]-h[l]));
if(mx > timer) return false;
if(l == a) {
return os(b,h[b]-h[a]);
} else if(l == b) {
return so(a,h[a]-h[b]);
} else {
if(!so(a,h[a]-h[l])) return false;
if(!os(b,h[b]-h[l])) return false;
if(val[gp(a,h[a]-h[l]-1)] > val[gp(b,h[b]-h[l]-1)]) return false;
return true;
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m; m += n-1;
timer = 1;
while(timer <= m) {
char c; cin>>c; assert(c != 'C');
int a,b; cin>>a>>b;
if(c == 'S') {
G[a].pb({b,timer});
G[b].pb({a,timer});
}
quer.emplace_back(c,a,b,timer);
timer ++;
}
dfsset(1);
timer = 1;
for(query q : quer) {
if(q.c == 'S') {
timer ++;
continue;
}
cout<< (ok(q.b,q.a) ? "yes":"no") << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
35016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
35016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
34964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
34964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
35060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
35060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
35016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
35016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
35028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
35028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
35020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
35020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
