Submission #1034121

#TimeUsernameProblemLanguageResultExecution timeMemory
1034121vjudge1Jail (JOI22_jail)C++17
0 / 100
10 ms14776 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define int long long #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) typedef long long ll; typedef pair<int,int> pii; typedef double ld; typedef pair<ld,ld> pdd; const int maxn=12e4+23; int n,m; int pos[maxn]; vector<int> ke[maxn],adj[maxn*4]; int Count,deg[maxn*4]; int heavy[maxn],par[maxn][21],in[maxn],out[maxn],dep[maxn],Time,head[maxn],rev[maxn]; vector<pii> el; int dd[maxn*4]; void lca(int u,int v) { while (u!=v) { if (u<v) swap(u,v); u/=2; } while(u!=1) { dd[u]++; // cerr<< u<<'\n'; u/=2; } dd[u]++; } void reset() { for1(i,0,n+1) { ke[i].clear(); } for1(i,0,max(n*4+1,Count+1)) { deg[i]=0; adj[i].clear(); dd[i]=0; } Time=0; Count=0; } void Build(int id=1,int l=1,int r=n) { // cerr<<"skrt "<< id<<' '<<l<<' '<<r<<'\n'; Count++; if (l==r) { pos[rev[l]]=id; return; } int mid=l+r>>1; Build(id*2,l,mid); Build(id*2+1,mid+1,r); adj[id].pb(id*2); adj[id].pb(id*2+1); // cerr<< id<<" -> "<<id*2<<'\n'; // cerr<< id<<" -> "<<id*2+1<<'\n'; deg[id*2]++; deg[id*2+1]++; } void Add(int node,int u,int v,int id=1,int l=1,int r=n) { if (u>r || v<l) return; if (u<=l && r<=v) { // adj[node].pb(id); el.pb({node,id}); // cerr<< node<<" -> "<<id<<'\n'; deg[id]++; return; } int mid=l+r>>1; Add(node,u,v,id*2,l,mid); Add(node,u,v,id*2+1,mid+1,r); } int predfs(int u=1, int pre=1) { int sz=1; int sz_mx=1; for(int v:ke[u]) { if (v==pre) continue; dep[v]=dep[u]+1; int sz_v=predfs(v,u); if (sz_v >= sz_mx) heavy[u]=v; sz+=sz_v; } return sz; } void hld(int u=1,int pre=1,int hd=1) { // cerr<< u<<" s\n"; in[u]=++Time; rev[Time]=u; head[u]=hd; par[u][0]=pre; for1(i,1,20) par[u][i]=par[par[u][i-1]][i-1]; if (heavy[u]!=-1) hld(heavy[u],u,hd); for(int v:ke[u]) { if (v==pre || v==heavy[u]) continue; hld(v,u,v); } out[u]=Time; } bool is_ancestor(int u,int v) {return in[u]<=in[v] && out[v]<=out[u];} int jump(int u,int v) { for2(i,20,0) if (!is_ancestor(par[v][i],u)) v=par[v][i]; return v; } void Update_hld(int node, int u, int v) { // cerr<< " ru\n"; while (head[u]!=head[v]) { if (dep[head[u]]<dep[head[v]]) swap(u,v); Add(node, in[head[u]], in[u]); // cerr<< node<<' '<<head[u]<<' '<<u<<" ok\n"; u=par[head[u]][0]; } if (dep[u]> dep[v]) swap(u,v); // cerr<<node<<' '<<u<<' '<<v<< " ok\n"; Add(node,in[u],in[v]); } void sol() { cin >> n; reset(); for1(i,1,n-1) { int u,v;cin >>u>>v; ke[u].pb(v); ke[v].pb(u); } for1(i,1,n) heavy[i]=-1; predfs(); // cerr<< "mf\n"; // cerr<< heavy[1]<<" q wd\n"; hld(); Build(); cin >> m; for1(i,1,m) { int s,t;cin >> s>> t; if (is_ancestor(s,t)) { int ss=jump(s,t); // cerr<<ss<< " sir?\n"; Update_hld(pos[s],ss,t); } else { Update_hld(pos[s],par[s][0],t); // cerr<<"zz "<< par[s][0]<<' '<<t<<'\n'; } } // cerr<< el.size()<<'\n'; for(auto [u,v]: el) { // int uu; // if (is_ancestor(u,v)) uu=jump(u,v); // else uu=par[u][0]; lca(u,v); // cerr<< u<<' '<<v<<" gg\n"; } for(auto [u,v]: el) { if (dd[v]) { cout << "No\n"; return; } adj[u].pb(v); } // for1(i,1,n) // { // cerr<<"zzz "<< i<<' '<<in[i]<<' '<<head[i]<<'\n'; // } // cerr<< Count<<'\n'; vector<int> L; if (deg[1]!=0) { cout << "No\n"; return; } L.pb(1); int g=0; while (!L.empty()) { int u=L.back(); // cerr<<"wa "<< u<<' '<<deg[u]<<'\n'; L.pop_back(); g++; for(int v:adj[u]) { --deg[v]; if (deg[v]==0) L.pb(v); // if (u==1) cerr<<"as "<< v<<'\n'; } } if (Count!=g) cout << "No\n"; else cout << "Yes\n"; // for1(i,1,Count) cout<<"za " << i<<' '<<deg[i]<<'\n'; // cerr<< g<<'\n'; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("jail.inp","r",stdin); // freopen("jail.out","w",stdout); int t=1;cin >> t; while (t--) sol(); } /* 2 3 1 2 1 3 2 1 1 1 2 7 1 2 1 3 3 4 4 5 3 6 6 7 2 3 4 5 6 */ /* 2 18 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 5 17 5 12 1 10 15 11 17 6 14 20 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 1 20 8 */

Compilation message (stderr)

jail.cpp: In function 'void Build(long long int, long long int, long long int)':
jail.cpp:63:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid=l+r>>1;
      |             ~^~
jail.cpp: In function 'void Add(long long int, long long int, long long int, long long int, long long int, long long int)':
jail.cpp:84:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid=l+r>>1;
      |             ~^~
#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...