Submission #814794

#TimeUsernameProblemLanguageResultExecution timeMemory
814794WonderfulWhaleJail (JOI22_jail)C++17
0 / 100
13 ms6360 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t #define pii pair<int, int> #define st first #define nd second #define pb push_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() vector<int> G[120009]; vector<int> G2[120009]; int tin[120009], tout[120009], T; int jp2[120009][20]; int deg[120009]; pii tab[120009]; void dfs(int x, int y) { tin[x] = ++T; jp2[x][0] = y; for(int i=1;i<20;i++) jp2[x][i] = jp2[jp2[x][i-1]][i-1]; for(int z:G[x]) if(z!=y) dfs(z, x); tout[x] = ++T; } bool is_ancestor(int x, int y) { return tin[x]<=tin[y]&&tout[x]>=tout[y]; } int lca(int x, int y) { if(is_ancestor(x, y)) return x; if(is_ancestor(y, x)) return y; for(int i=19;i>=0;i--) { if(!is_ancestor(jp2[x][i], y)) { x = jp2[x][i]; } } return jp2[x][0]; } bool is_on_path(int x, int a, int b) { return is_ancestor(a, x)&&is_ancestor(x, b); } bool f(int x, int a, int b) { int y = lca(a, b); //cerr << "lca: " << a << " " << b << " " << y << "\n"; //cerr << "checking: " << x << " " << a << " " << b << " " << (is_on_path(x, y, a)||is_on_path(x, y, b)) << "\n"; return is_on_path(x, y, a)||is_on_path(x, y, b); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int q=1; cin >> q; while(q--) { int n, m; cin >> n; for(int i=1;i<=n;i++) G[i].clear(); for(int i=0;i<n-1;i++) { int a, b; cin >> a >> b; G[a].pb(b); G[b].pb(a); } tin[0] = T = 0; dfs(1, 0); tout[0] = T; cin >> m; for(int i=0;i<m;i++) { G2[i].clear(); deg[i] = 0; } for(int i=0;i<m;i++) { cin >> tab[i].st >> tab[i].nd; } for(int i=0;i<m;i++) { for(int j=0;j<m;j++) { if(i==j) continue; if(f(tab[j].st, tab[i].st, tab[i].nd)) { //cerr << "adding: " << i << " " << j << "\n"; G2[i].pb(j); deg[j]++; } } } int cnt = 0; queue<int> Q; for(int i=0;i<m;i++) { if(deg[i]==0) { Q.push(i); } } while(sz(Q)) { cnt++; int x = Q.front(); Q.pop(); for(int y:G2[x]) { deg[y]--; if(deg[y]==0) Q.push(y); } } if(cnt==m) { cout << "Yes\n"; } else { cout << "No\n"; } } }
#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...