이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
v<v<int>> adj;
v<int> pathstarts;
v<int> pathends;
v<set<int>> sets;
v<v<int>> diadj;
void dfs(int cur, int par){
for(int it:adj[cur]){
if(it==par) continue;
dfs(it, cur);
for(int i:sets[it]){
if(i<0) continue;
if(sets[it].find(-1-i)!=sets[it].end()) continue;
if(sets[cur].find(i)==sets[cur].end()) sets[cur].insert(i);
else sets[cur].insert(-1-i);
if(pathstarts[cur]!=-1 && pathstarts[cur]!=i){
//cout<<"start of path "<<pathstarts[cur]<<" lies on path "<<i<<endl;
diadj[pathstarts[cur]].push_back(i);
}
if(pathends[cur]!=-1 && pathends[cur]!=i){
//cout<<"end of path "<<pathends[cur]<<" lies on path "<<i<<endl;
diadj[i].push_back(pathends[cur]);
}
}
}
if(pathstarts[cur]!=-1){
if(sets[cur].find(pathstarts[cur])==sets[cur].end()) sets[cur].insert(pathstarts[cur]);
else sets[cur].insert(-1-pathstarts[cur]);
}
if(pathends[cur]!=-1){
if(sets[cur].find(pathends[cur])==sets[cur].end()) sets[cur].insert(pathends[cur]);
else sets[cur].insert(-1-pathends[cur]);
}
if(pathstarts[cur]!=-1 && pathends[cur]!=-1){
//cout<<"end of path "<<pathends[cur]<<" lies on path "<<pathstarts[cur]<<endl;
diadj[pathstarts[cur]].push_back(pathends[cur]);
}
for(int it:adj[cur]){
if(it==par) continue;
sets[it].clear();
}
}
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);
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);
}
cin>>M;
pathstarts = v<int>(N,-1);
pathends=v<int>(N,-1);
for(int i=0; i<M; i++){
int s,e;
cin>>s>>e;
s--;
e--;
pathstarts[s]=i;
pathends[e]=i;
}
diadj = v<v<int>>(M);
sets = v<set<int>>(N);
dfs(0,0);
bool cycle=false;
vis = v<bool>(M,false);
prevrec = v<bool>(M,false);
for(int i=0; i<M; i++){
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... |