Submission #927298

#TimeUsernameProblemLanguageResultExecution timeMemory
927298andrei_boacaJail (JOI22_jail)C++17
61 / 100
5043 ms32832 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; 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]; map<pii,int> f; 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; } bool onchain(int x,int a,int b) { return dist(a,x)+dist(x,b)==dist(a,b); } 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; } f.clear(); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(i!=j) { if(onchain(A[j],A[i],B[i])) { edges[j].push_back(i); grad[i]++; } if(onchain(B[j],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...