Submission #927291

#TimeUsernameProblemLanguageResultExecution timeMemory
927291andrei_boacaJail (JOI22_jail)C++17
0 / 100
3 ms18780 KiB
#include <bits/stdc++.h> using namespace std; int t,n,m,A[120005],B[120005],in[120005],out[120005],timp,par[120005],niv[1200005],dp[21][120005]; vector<int> muchii[120005]; vector<int> edges[120005]; bool isancestor(int a,int b) { return in[a]<=in[b]&&out[a]>=out[b]; } int LCA(int a,int b) { if(niv[a]>niv[b]) swap(a,b); if(isancestor(a,b)) return a; for(int i=18;i>=0;i--) if(dp[i][a]!=0&&!isancestor(dp[i][a],b)) a=dp[i][a]; return par[a]; } int dist(int a,int b) { int lca=LCA(a,b); return niv[a]+niv[b]-2*niv[lca]; } void dfs(int nod) { timp++; in[nod]=timp; dp[0][nod]=par[nod]; for(int i=1;i<=18;i++) dp[i][nod]=dp[i-1][dp[i-1][nod]]; for(int i:muchii[nod]) if(i!=par[nod]) { par[i]=nod; niv[i]=niv[nod]+1; dfs(i); } out[nod]=timp; } int grad[120005]; void solve() { cin>>n; timp=0; for(int i=1;i<=n;i++) muchii[i].clear(); for(int i=1;i<n;i++) { int a,b; cin>>a>>b; muchii[a].push_back(b); muchii[b].push_back(a); } dfs(1); cin>>m; for(int i=1;i<=m;i++) { cin>>A[i]>>B[i]; edges[i].clear(); grad[i]=0; } for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) if(i!=j) { if(dist(A[i],A[j])+dist(A[j],B[i])==dist(A[i],B[i])) { edges[j].push_back(i); grad[i]++; } if(dist(A[i],B[j])+dist(B[j],B[i])==dist(A[i],B[i])) { edges[i].push_back(j); grad[j]++; } } queue<int> coada; int cnt=0; for(int i=1;i<=m;i++) if(grad[i]==0) coada.push(i); while(!coada.empty()) { int nod=coada.front(); coada.pop(); cnt++; for(int i:edges[nod]) { grad[i]--; if(grad[i]==0) coada.push(i); } } if(cnt==m) cout<<"Yes\n"; else cout<<"No\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>t; while(t--) 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...