Submission #1001137

#TimeUsernameProblemLanguageResultExecution timeMemory
1001137De3b0oJail (JOI22_jail)C++14
21 / 100
5098 ms14468 KiB
#include<bits/stdc++.h> #define ll long long #define F first #define S second #define in insert #define pb push_back #define ppb pop_back() #define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define cans cout << ans << "\n"; #define yes cout << "Yes" << "\n"; #define no cout << "No" << "\n"; #define pll pair<ll,ll> #define lin cout << "\n"; #define mod 1000000007 #define mid ((l+r)/2) #define lc (2*x) #define rc (2*x+1) using namespace std; ll n , m; vector<ll> adj[120009]; ll S[120009] , T[120009]; vector<ll> path[120009]; set<ll> pas[120009]; ll pr[120009]; void dfs(ll x , ll p , ll f , ll s) { pr[x]=p; if(x==f) { ll y = f; while(y) { path[s].pb(y); pas[s].in(y); y=pr[y]; } reverse(path[s].begin(),path[s].end()); return; } for(auto it : adj[x]) { if(it==p) continue; dfs(it,x,f,s); } } int main() { d3 ll t; cin >> t; while(t--) { cin >> n; for(int i = 1 ; n>=i ; i++) adj[i].clear(); for(int i = 0 ; n-1>i ; i++) { ll u , v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } cin >> m; for(int i = 1 ; m>=i ; i++) { cin >> S[i] >> T[i]; path[i].clear(); pas[i].clear(); dfs(S[i],0,T[i],i); } bool ans = 0; ll a[m]; for(int i = 0 ; m>i ; i++) a[i]=i+1; do { bool g = 1; for(int i = 0 ; m>i ; i++) { for(int j = i+1 ; m>j ; j++) { if(pas[a[i]].find(S[a[j]])!=pas[a[i]].end()) g=0; } for(int j = i-1 ; j>=0 ; j--) { if(pas[a[i]].find(T[a[j]])!=pas[a[i]].end()) g=0; } } if(g) ans=1; } while(next_permutation(a,a+m)); if(ans) yes else no } }
#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...