Submission #1054978

#TimeUsernameProblemLanguageResultExecution timeMemory
1054978hotboy2703Prize (CEOI22_prize)C++17
29 / 100
3513 ms286668 KiB
#include<bits/stdc++.h> using ll = int; using namespace std; #define pll pair <ll,ll> #define fi first #define se second #define MP make_pair #define sz(a) (ll((a).size())) #define BIT(mask,i) (((mask) >> (i))&1) #define MASK(i) (1LL << (i)) const ll MAXN = 5e5+100; const ll MAXK = 19; ll n,k,q,t; struct tree{ vector <ll> g[MAXN]; ll depth[MAXN]; ll sp[MAXN][MAXK]; vector <pll> adj[MAXN]; ll dp[MAXN]; vector <ll> choose; ll in[MAXN],timeDFS; void dfs(ll u,ll p){ sp[u][0] = p; in[u] = ++timeDFS; for (ll j = 1;j < MAXK;j ++){ sp[u][j] = sp[sp[u][j-1]][j-1]; } depth[u] = depth[p]+1; choose.push_back(u); for (auto v:g[u]){ if (v==p)continue; dfs(v,u); } } ll lca(ll u,ll v){ if (depth[u] > depth[v])swap(u,v); for (ll j = MAXK-1;j >= 0;j --){ if (depth[sp[v][j]] >= depth[u])v = sp[v][j]; } if (u==v)return u; for (ll j = MAXK-1;j >= 0;j--){ if (sp[v][j] != sp[u][j])u = sp[u][j],v = sp[v][j]; } return sp[u][0]; } ll root=-1; void add(ll u,ll v,ll wu,ll wv){ ll LCA = lca(u,v); if (root==-1||depth[LCA]<depth[root])root=LCA; adj[LCA].push_back(MP(u,wu)); adj[u].push_back(MP(LCA,wu)); adj[LCA].push_back(MP(v,wv)); adj[v].push_back(MP(LCA,wv)); } void solve(){ // for (ll i = 1;i <= n;i ++){ // if (dp[i] == 0){ queue <ll> q; q.push(root); while (!q.empty()){ ll u = q.front(); q.pop(); for (auto [v,w]:adj[u]){ if (v != u && dp[v] == 0){ dp[v] = dp[u] + (depth[u] > depth[v] ? -1 : + 1) * w; q.push(v); } } } // } // } } ll query(ll u,ll v){ ll LCA = lca(u,v); return dp[u] + dp[v] - dp[LCA]*2; } } a1,a2; int main(){ ios_base::sync_with_stdio(0);cin.tie(nullptr); cin>>n>>k>>q>>t; ll r1,r2; for (ll i = 1;i <= n;i ++){ ll x; cin>>x; if (x!=-1){ a1.g[x].push_back(i); a1.g[i].push_back(x); } else r1 = i; } for (ll i = 1;i <= n;i ++){ ll x; cin>>x; if (x!=-1){ a2.g[x].push_back(i); a2.g[i].push_back(x); } else r2 = i; } a1.dfs(r1,r1); a2.dfs(r2,r2); vector <ll> c = a1.choose; c.resize(k); sort(c.begin(),c.end(),[](ll x,ll y){return a2.in[x] < a2.in[y];}); for (auto x:c)cout<<x<<' '; cout<<'\n'; for (ll j = 0;j + 1 < sz(c);j ++)cout<<"? "<<c[j]<<' '<<c[j+1]<<'\n'; cout<<'!'<<endl; for (ll j = 0;j + 1 < sz(c);j ++){ ll u1,v1,u2,v2; cin>>u1>>v1>>u2>>v2; a1.add(c[j],c[j+1],u1,v1); a2.add(c[j],c[j+1],u2,v2); } // return 0; a1.solve(),a2.solve(); // return 0; vector <pll> ans; while (t--){ ll x,y; cin>>x>>y; ans.push_back(MP(a1.query(x,y),a2.query(x,y))); // cout<<a1.query(x,y)<<' '<<a2.query(x,y)<<'\n'; } for (auto x:ans)cout<<x.fi<<' '<<x.se<<'\n'; cout.flush(); }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:8: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |  a1.dfs(r1,r1);
      |  ~~~~~~^~~~~~~
Main.cpp:102:8: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |  a2.dfs(r2,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...