#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
struct qT {
int type;
int a;
int d;
int t;
qT(int _type,int _a,int _d,int _t):type(_type),a(_a),d(_d),t(_t) {}
};
const int N = 120005;
vector<pair<int,int> > side[N];
static const int B = 20;
int P[N][B];
pair<int,int> mx[N][B];
pair<int,int> mi[N][B];
pair<int,int> dfn[N];
struct Qstruct {
int n;
int T;
void dfs(int cur,int p,int v) {
dfn[cur].first=++T;
P[cur][0]=p;
mx[cur][0]={v,cur};
mi[cur][0]={v,cur};
for(auto e : side[cur]) {
if(e.first!=p) dfs(e.first,cur,e.second);
}
dfn[cur].second=++T;
}
void init(int _n){
T=0;
n=_n;
dfs(1,1,0);
for(int j=0;j<B;j++){
P[1][j]=1;
mx[1][j]={-1e9,1};
mi[1][j]={1e9,1};
}
for(int j=1;j<B;j++){
for(int i=2;i<=n;i++){
P[i][j] = P[P[i][j-1]][j-1];
mx[i][j] = max(mx[i][j-1],mx[P[i][j-1]][j-1]);
mi[i][j] = min(mi[i][j-1],mi[P[i][j-1]][j-1]);
}
}
}
bool isanc(int a,int b){
return ((dfn[a].first<=dfn[b].first)&&(dfn[a].second>=dfn[b].second));
}
int lca(int a,int b){
if(isanc(a,b)) return a;
if(isanc(b,a)) return b;
for(int j=B-1;j>=0;j--){
if(!isanc(P[b][j],a)) b = P[b][j];
}
return P[b][0];
}
pair<pair<int,int>,pair<int,int> > get(int a,int d){
assert(isanc(a,d));
assert(a!=d);
pair<int,int> maxn = {-1e9,-1};
pair<int,int> minn = {1e9,-1};
for(int j=B-1;j>=0;j--){
if(!isanc(P[d][j],a)){
maxn = max(maxn,mx[d][j]);
minn = min(minn,mi[d][j]);
d = P[d][j];
}
}
maxn = max(maxn,mx[d][0]);
minn = min(minn,mi[d][0]);
return {minn,maxn};
}
bool query(int a,int d,int t){
if(a==d) return 1;
if(isanc(a,d)){
auto [minn,maxn] = get(a,d);
if((minn.second!=d || P[maxn.second][0]!=a)) return 0;
if(maxn.first>t) return 0;
return 1;
}
if(isanc(d,a)){
auto [minn,maxn] = get(d,a);
if(maxn.second!=a || P[minn.second][0]!=d) return 0;
if(maxn.first>t) return 0;
return 1;
}
int c = lca(a,d);
auto [mina,maxa] = get(c,a);
auto [mind,maxd] = get(c,d);
if(mind.second!=d || P[maxd.second][0]!=c) return 0;
if(maxa.second!=a || P[mina.second][0]!=c) return 0;
if(max(maxa.first,maxd.first)>t) return 0;
return maxd.first<mina.first;
}
};
int main() {
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,k;
cin>>n>>k;
vector<qT> query;
for(int i=1; i<=n+k-1; i++) {
char t;
cin>>t;
if(t=='S') {
int a,b;
cin>>a>>b;
side[a].push_back({b,i});
side[b].push_back({a,i});
}
if(t=='Q') {
int a,d;
cin>>a>>d;
query.emplace_back(0,a,d,i);
}
if(t=='C') {
int d;
cin>>d;
query.emplace_back(1,0,d,i);
}
}
Qstruct Qans;
Qans.init(n);
for(auto cur : query) {
if(cur.type==0) {
if(Qans.query(cur.a,cur.d,cur.t)){
cout<<"yes\n";
}else{
cout<<"no\n";
}
} else {
cout<<0<<"\n";
}
}
return 0;
}
/*
6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
6356 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
8592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
6356 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
8592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
6588 KB |
Output is correct |
| 2 |
Correct |
185 ms |
60852 KB |
Output is correct |
| 3 |
Correct |
180 ms |
60856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
6588 KB |
Output is correct |
| 2 |
Correct |
185 ms |
60852 KB |
Output is correct |
| 3 |
Correct |
180 ms |
60856 KB |
Output is correct |
| 4 |
Incorrect |
38 ms |
6348 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
6352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
6352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
6352 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
8632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
6352 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
8632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
