#include<bits/stdc++.h>
using namespace std;
const int N=120050;
const int Q=240050;
const bool DEBUG=0;
int n,k,sz[N],u[Q],v[Q];
char ty[Q];
bool del[N];
map<pair<int,int>,int> t;
map<int,int> tonde[N],frmnde[N],incen[N];
vector<int> adj[N];
void prec(int nde,int par){
sz[nde]=1;
for (int i:adj[nde]){
if (del[i]) continue;
if (i==par) continue;
prec(i,nde);
sz[nde]+=sz[i];
}
}
int findcen(int nde,int par,int mx){
for (int i:adj[nde]){
if (del[i]) continue;
if (i==par) continue;
if (sz[i]>=mx/2) return findcen(i,nde,mx);
}
return nde;
}
void comp(int nde,int par,int smallrt,int bigrt,int mindist,int mxdist){
if (DEBUG) cerr<<nde<<":"<<par<<" "<<smallrt<<","<<bigrt<<"::"<<mindist<<","<<mxdist<<"\n";
incen[nde][bigrt]=smallrt;
tonde[bigrt][nde]=mxdist;
frmnde[bigrt][nde]=mindist;
for (int i:adj[nde]){
if (del[i]) continue;
if (i==par) continue;
if (t[{nde,i}]>mxdist){
comp(i,nde,smallrt,bigrt,INT_MIN,t[{nde,i}]);
}else if (t[{nde,i}]<mindist){
comp(i,nde,smallrt,bigrt,t[{nde,i}],INT_MAX);
}else{
comp(i,nde,smallrt,bigrt,INT_MIN,INT_MAX);
}
}
}
void dc(int nde){
prec(nde,nde);
int cen=findcen(nde,nde,sz[nde]);
if (DEBUG) cerr<<nde<<":"<<cen<<"uwuuwu\n";
del[cen]=1;
for (int i:adj[cen]){
if (del[i]) continue;
comp(i,cen,i,cen,t[{cen,i}],t[{cen,i}]);
}
for (int i:adj[cen]){
if (del[i]) continue;
dc(i);
}
}
bool check(int rt,int v,int u,int id){
// v->u
if (u==rt){
if (frmnde[rt][v]==INT_MIN) return 0;
return (frmnde[rt][v]<=id);
}else if (v==rt){
if (tonde[rt][u]==INT_MAX) return 0;
return (tonde[rt][u]<=id);
}else{
if (incen[u][rt]==incen[v][rt]) return 0;
if (t[{incen[v][rt],rt}]>t[{incen[u][rt],rt}]) return 0;
if (frmnde[rt][v]==INT_MIN) return 0;
if (tonde[rt][u]>id) return 0;
return 1;
}
}
int main(){
cin>>n>>k;
for (int i=1;i<n+k;i++){
cin>>ty[i]>>u[i];
if (ty[i]=='S'){
cin>>v[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
t[{u[i],v[i]}]=i;
t[{v[i],u[i]}]=i;
}else if (ty[i]=='Q'){
cin>>v[i];
}else{
//???
}
}
dc(1);
for (int i=1;i<n+k;i++){
if (ty[i]=='Q'){
//check if v->u exists
if (u[i]==v[i]){
cout<<"yes\n";
goto skip;
}
if (DEBUG) cerr<<v[i]<<",,"<<u[i]<<"\n";
for (auto j:incen[v[i]]){
if (!j.second) continue;
if (DEBUG) cerr<<j.first<<"::"<<j.second<<"a\n";
if ((!!incen[u[i]][j.first])||j.first==u[i]){
if (DEBUG) cerr<<v[i]<<"->"<<incen[v[i]][j.first]<<"--"<<j.first<<"--"<<incen[u[i]][j.first]<<"->"<<u[i]<<"\n";
if (check(j.first,v[i],u[i],i)){
cout<<"yes\n";
goto skip;
}
}
}
if (incen[u[i]][v[i]]){
if (check(v[i],v[i],u[i],i)){
cout<<"yes\n";
goto skip;
}
}
cout<<"no\n";
skip:;
}else if (ty[i]=='C'){
cout<<"42\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
22360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
22360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22468 KB |
Output is correct |
| 2 |
Correct |
860 ms |
64840 KB |
Output is correct |
| 3 |
Correct |
842 ms |
64800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
22468 KB |
Output is correct |
| 2 |
Correct |
860 ms |
64840 KB |
Output is correct |
| 3 |
Correct |
842 ms |
64800 KB |
Output is correct |
| 4 |
Incorrect |
106 ms |
22488 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
22360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
22360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
22464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
22464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
22388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
22388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
22412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
22412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
