# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
545180 |
2022-04-03T21:05:19 Z |
inksamurai |
Jail (JOI22_jail) |
C++17 |
|
1 ms |
216 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
void slv(){
int n;
cin>>n;
vec(vi) adj(n);
rep(i,n-1){
int u,v;
cin>>u>>v;
u-=1,v-=1;
adj[u].pb(v);
adj[v].pb(u);
}
int m;
cin>>m;
vi to(n,-1),ids(n,-1),idt(n,-1);
rep(i,m){
int s,t;
cin>>s>>t;
s-=1,t-=1;
assert(ids[s]==-1);
assert(idt[t]==-1);
ids[s]=i;
idt[t]=i;
to[s]=t;
}
int s;
vec(vi) gr(m);
auto walk=[&](auto self,int v,int par,int t)->bool{
bool type=0;
for(auto u:adj[v]){
if(u==par) continue;
type=type or self(self,u,v,t);
}
type=type or v==t;
if(type){
if(s!=v and ids[v]!=-1){
gr[ids[v]].pb(ids[s]);
}
if(s!=v and v!=t and idt[v]!=-1){
gr[ids[s]].pb(idt[v]);
}
}
return type;
};
rep(v,n){
if(to[v]!=-1){
s=v;
walk(walk,v,-1,to[v]);
}
}
vi usd(m,0),usd1(m,0);
bool cyc=0;
auto dfs=[&](auto self,int v,int par)->void{
usd[v]=1;
usd1[v]=1;
for(auto u:gr[v]){
if(u==par) continue;
if(usd1[u]){
cyc=1;
}
if(!usd[u]){
self(self,u,v);
}
}
usd1[v]=0;
};
// rep(v,n){
// print(v);
// for(auto u:gr[v]){
// cout<<u<<" ";
// }
// cout<<"\n";
// }
rep(v,m){
if(!usd[v]){
dfs(dfs,0,-1);
}
}
cout<<(cyc?"No":"Yes")<<"\n";
}
signed main(){
_3x2WzQf;
int t;
cin>>t;
rep(cs,t){
slv();
}
//
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
216 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |