이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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],t[N],preord[N],postord[N],pt;
char ty[Q];
bool del[N];
map<int,int> tonde[N],frmnde[N],incen[N];
vector<int> adj[N];
void mainprec(int nde,int par){
preord[nde]=++pt;
for (int i:adj[nde]) if (i!=par) mainprec(i,nde);
postord[nde]=pt;
}
bool isa(int a,int b){
return (preord[a]<=preord[b]&&postord[a]>=postord[b]);
}
int qedge(int a,int b){
return (isa(a,b)?t[b]:t[a]);
}
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 (qedge(nde,i)>mxdist){
comp(i,nde,smallrt,bigrt,INT_MIN,qedge(nde,i));
}else if (qedge(nde,i)<mindist){
comp(i,nde,smallrt,bigrt,qedge(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,qedge(cen,i),qedge(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 (qedge(rt,incen[v][rt])<=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 (qedge(incen[v][rt],rt)>qedge(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.tie(0)->sync_with_stdio(0);
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]);
}else if (ty[i]=='Q'){
cin>>v[i];
}else{
//???
}
}
mainprec(1,1);
for (int i=1;i<n+k;i++){
if (ty[i]!='S') continue;
if (isa(u[i],v[i])) t[v[i]]=i;
else t[u[i]]=i;
}
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |