This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <iostream>
#include <utility>
#include <set>
#include <algorithm>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
int N,M;
int anc=20;
v<v<int>> adj;
v<int> depth;
v<v<int>> par;
v<int> ps;
v<int> pe;
v<v<int>> num;
void dfs(int cur, int from){
if(depth[cur]!=-1) return;
depth[cur]=depth[from]+1;
par[cur][0]=from;
if(ps[cur]!=-1) num[cur][0]++;
if(pe[cur]!=-1) num[cur][0]++;
for(int it:adj[cur]) dfs(it, cur);
}
bool is_anc(int cur, int other){
for(int i=anc-1; i>=0; i--){
if(depth[par[cur][i]]>=depth[other]) cur=par[cur][i];
}
if(cur==other) return true;
return false;
}
int lca(int a, int b){
if(depth[a]<depth[b]) swap(a,b);
for(int i=anc-1; i>=0; i--){
if(depth[par[a][i]]>=depth[b]) a=par[a][i];
}
if(a==b) return a;
for(int i=anc-1; i>=0; i--){
if(par[a][i]!=par[b][i]){
a=par[a][i];
b=par[b][i];
}
}
return par[a][0];
}
v<set<int>> diadj;
v<bool> prevrec;
v<bool> vis;
bool find_cycle(int cur){
if(!vis[cur]){
vis[cur]=true;
prevrec[cur]=true;
for(int it:diadj[cur]){
if(!vis[it] && find_cycle(it)){
return true;
}
else if(prevrec[it]){
return true;
}
}
}
prevrec[cur]=false;
return false;
}
int main(){
int Q;
cin>>Q;
for(int q=0;q<Q;q++){
cin>>N;
adj=v<v<int>>(N);
bool subone=true;
for(int i=0; i<N-1; i++){
int a,b;
cin>>a>>b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
if(a+1!=b) subone=false;
}
if(subone){
cin>>M;
v<pii> rooms(M);
v<pii> rooms2(M);
for(int i=0; i<M; i++){
int a,b;
cin>>a>>b;
if(b>=a){
rooms.push_back({a,b});
rooms2.push_back({-a,b});
rooms2.push_back({-b,a});
}
else{
rooms.push_back({a,-b});
rooms.push_back({b,-a});
rooms2.push_back({-a,-b});
}
}
sort(rooms.begin(), rooms.end());
sort(rooms2.begin(),rooms2.end());
pii cur={-1,-1};
pii def={-1,-1};
bool out=true;
for(pii it:rooms){
if(it.se<=0){
if(cur!=def && cur.se>=it.fi){
out=false;
break;
}
}
else{
if(it.se<cur.se){
out=false;
break;
}
cur=it;
}
}
cur={1,1};
def={1,1};
for(pii it:rooms2){
if(it.se>=0){
if(cur!=def && cur.se>=it.fi){
out=false;
break;
}
}
else{
if(it.se<cur.se && cur!=def){
out=false;
break;
}
cur=it;
}
}
if(out) cout<<"Yes\n";
else cout<<"No\n";
continue;
}
cin>>M;
v<pii> rooms(M);
ps = v<int>(N,-1);
pe = v<int>(N,-1);
for(int i=0; i<M; i++){
cin>>rooms[i].fi>>rooms[i].se;
rooms[i].fi--;
rooms[i].se--;
ps[rooms[i].fi]=i;
pe[rooms[i].se]=i;
}
depth=v<int>(N,-1);
par=v<v<int>>(N,v<int>(anc,-1));
num=v<v<int>>(N,v<int>(anc,0));
dfs(0,0);
for(int i=1; i<anc; i++){
for(int j=0; j<N; j++){
par[j][i]=par[par[j][i-1]][i-1];
num[j][i]=num[par[j][i-1]][i-1]+num[j][i-1];
}
}
bool cycle=false;
diadj = v<set<int>>(M);
for(int i=0; i<M; i++){
int a=rooms[i].fi;
int b=rooms[i].se;
int l=lca(a,b);
while(true){
for(int j=anc-1; j>=0; j--){
if(depth[par[a][j]]<depth[l]) continue;
if(num[a][j]==0) a=par[a][j];
}
if(ps[a]!=-1 && ps[a]!=i) diadj[ps[a]].insert(i);
if(pe[a]!=-1 && pe[a]!=i) diadj[i].insert(pe[a]);
if(a==l) break;
a=par[a][0];
}
while(b!=l){
for(int j=anc-1; j>=0; j--){
if(depth[par[b][j]]<=depth[l]) continue;
if(num[b][j]==0) b=par[b][j];
}
if(ps[b]!=-1 && ps[b]!=i) diadj[ps[b]].insert(i);
if(pe[b]!=-1 && pe[b]!=i) diadj[i].insert(pe[b]);
b=par[b][0];
}
for(int it:diadj[i]){
if(diadj[it].find(i)!=diadj[it].end()) cycle=true;
if(cycle) break;
/**for(int jt:diadj[it]){
if(diadj[jt].find(i)!=diadj[jt].end()) cycle=true;
if(cycle) break;
}
if(cycle) break;**/
}
if(cycle) break;
}
vis = v<bool>(M,false);
prevrec = v<bool>(M,false);
for(int i=0; i<M; i++){
if(cycle) break;
if(!vis[i] && find_cycle(i)){
cycle=true;
break;
}
}
if(cycle) cout<<"No\n";
else cout<<"Yes\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... |