Submission #858315

#TimeUsernameProblemLanguageResultExecution timeMemory
858315willychanJail (JOI22_jail)C++14
21 / 100
5084 ms600 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; //#include<bits/extc++.h> //__gnu_pbds const int N = 300; int p[N]; bool havestuff[N]; vector<int> side[N]; vector<pair<int,int> > qu; int n; int dep[N]; void dfs(int cur){ for(auto i : side[cur]) { if(p[i]) continue; p[i]=cur; dep[i]=dep[cur]+1; dfs(i); } } bool works(vector<int> &order){ for(auto i : order){ int a = qu[i].first; int b = qu[i].second; int og = b; havestuff[a]=0; while(a!=b){ if(dep[a]>dep[b]) swap(a,b); if(havestuff[b]) return 0; b = p[b]; } if(havestuff[b]) return 0; havestuff[og]=1; } return 1; } void solve(){ cin>>n; for(int i=1;i<=n;i++){ side[i].clear(); dep[i]=0; p[i]=0; } for(int i=0;i<n-1;i++){ int a,b;cin>>a>>b; side[a].push_back(b); side[b].push_back(a); } p[1]=1; dfs(1); int m; cin>>m; qu.resize(m); for(int i=0;i<m;i++) cin>>qu[i].first>>qu[i].second; vector<int> order(m); for(int i=0;i<m;i++) order[i]=i; do{ for(int i=1;i<=n;i++) havestuff[i]=0; for(int i=0;i<m;i++) havestuff[qu[i].first]=1; if(works(order)){ cout<<"Yes\n"; return ; } }while(next_permutation(order.begin(),order.end())); cout<<"No\n"; return ; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); int q;cin>>q; while(q--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...