Submission #653121

#TimeUsernameProblemLanguageResultExecution timeMemory
653121Rafi22Prize (CEOI22_prize)C++14
10 / 100
1967 ms430188 KiB
#include <bits/stdc++.h> using namespace std; //#define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll long long #define ld long double ll mod=1000000007; int inf=1000000007; ll infl=1000000000000000007; const int N=1000007; vector<int>G1[N],G2[N]; vector<pair<int,int>>G3[N]; int d1[N],d2[N]; bool odw[N]; vector<pair<int,int>>X[N]; bool is[N]; int n,k,q,t; int skok[N][20]; int pre[N]; int post[N]; int c=0; void dfs(int v,int o) { pre[v]=++c; skok[v][0]=o; for(int i=1;i<20;i++) skok[v][i]=skok[skok[v][i-1]][i-1]; if(k>0) { cout<<v<<" "; is[v]=1; k--; } for(auto u:G1[v]) dfs(u,v); post[v]=++c; } int lca(int u,int v) { if(pre[u]<=pre[v]&&post[u]>=post[v]) return u; if(pre[v]<=pre[u]&&post[v]>=post[u]) return v; for(int i=19;i>=0;i--) if(!(pre[skok[u][i]]<=pre[v]&&post[skok[u][i]]>=post[v])) u=skok[u][i]; return skok[u][0]; } vector<pair<pair<int,int>,int>>xd; void qry(int u,int v,int x) { cout<<"? "<<u<<" "<<v<<endl; xd.pb({{u,v},x}); /* */ } int last[N]; void dfs1(int v) { int l=0,c=0; for(auto u:G2[v]) { dfs1(u); if(last[u]>0) { c++; if(is[v]) qry(last[u],v,v); else if(c>1) qry(l,last[u],v); else l=last[u]; } } if(is[v]||c>1) last[v]=v; else if(c==1) last[v]=l; } int skok1[N][20]; int pre1[N]; int post1[N]; void dfs2(int v,int o) { pre1[v]=++c; skok1[v][0]=o; for(int i=1;i<20;i++) skok1[v][i]=skok1[skok1[v][i-1]][i-1]; for(auto u:G3[v]) { d2[u.st]=d2[v]+u.nd; dfs2(u.st,v); } post1[v]=++c; } int lca1(int u,int v) { if(pre1[u]<=pre1[v]&&post1[u]>=post1[v]) return u; if(pre1[v]<=pre1[u]&&post1[v]>=post1[u]) return v; for(int i=19;i>=0;i--) if(!(pre1[skok1[u][i]]<=pre1[v]&&post1[skok1[u][i]]>=post1[v])) u=skok1[u][i]; return skok1[u][0]; } int U[N],V[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>q>>t; int r1,r2,p; for(int i=1;i<=n;i++) { cin>>p; if(p==-1) r1=i; else G1[p].pb(i); } for(int i=1;i<=n;i++) { cin>>p; if(p==-1) r2=i; else G2[p].pb(i); } dfs(r1,r1); cout<<endl; dfs1(r2); cout<<"!"<<endl; for(auto c:xd) { int u=c.st.st,v=c.st.nd,x=c.nd; int d1,d2,d3,d4; cin>>d1>>d2>>d3>>d4; int l=lca(u,v); X[l].pb({u,d1}); X[u].pb({l,d1}); X[l].pb({v,d2}); X[v].pb({l,d2}); if(v!=x) G3[x].pb({v,d4}); G3[x].pb({u,d3}); } c=0; dfs2(last[r2],last[r2]); deque<int>Q; Q.pb(r1); odw[r1]=1; while(sz(Q)>0) { int v=Q[0]; Q.pop_front(); for(auto x:X[v]) { if(odw[x.st]) continue; odw[x.st]=1; Q.pb(x.st); if(pre[x.st]>=pre[v]) d1[x.st]=d1[v]+x.nd; else d1[x.st]=d1[v]-x.nd; } } for(int i=1;i<=t;i++) cin>>U[i]>>V[i]; for(int i=1;i<=t;i++) { int u=U[i],v=V[i]; int l=lca(u,v); cout<<d1[u]+d1[v]-2*d1[l]<<" "; l=lca1(u,v); cout<<d2[u]+d2[v]-2*d2[l]<<endl; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:151:12: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  151 |     odw[r1]=1;
      |     ~~~~~~~^~
Main.cpp:148:9: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  148 |     dfs2(last[r2],last[r2]);
      |     ~~~~^~~~~~~~~~~~~~~~~~~
#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...