Submission #727331

#TimeUsernameProblemLanguageResultExecution timeMemory
727331amunduzbaevPrize (CEOI22_prize)C++17
100 / 100
3180 ms551112 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef long long ll; #define int ll const int N = 1e6 + 5; vector<int> G[2][N]; int tin[2][N], tout[2][N], par[2][N][20]; int d[2][N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n, k, q, T; cin >> n >> k >> q >> T; int R[2] {}; for(int i=1;i<=n;i++){ int p; cin >> p; if(~p){ G[0][p].push_back(i); } else { R[0] = i; } } for(int i=1;i<=n;i++){ int p; cin >> p; if(~p){ G[1][p].push_back(i); } else { R[1] = i; } } for(int c=0;c<2;c++){ int t = 0; tout[c][0] = N; function<void(int)> dfs = [&](int u){ tin[c][u] = ++t; for(int j=1;j<20;j++){ par[c][u][j] = par[c][par[c][u][j-1]][j-1]; } for(auto x : G[c][u]){ par[c][x][0] = u; dfs(x); } tout[c][u] = t; }; dfs(R[c]); } vector<int> p; function<void(int)> dfs = [&](int u){ if(tin[0][u] <= k){ p.push_back(u); } for(auto x : G[0][u]){ dfs(x); } }; dfs(R[0]); for(auto x : p){ cout<<x<<" "; } cout<<endl; auto is = [&](int t, int a, int b){ return (tin[t][a] <= tin[t][b] && tin[t][b] <= tout[t][a]); }; auto Lca = [&](int t, int a, int b){ if(is(t, a, b)) return a; if(is(t, b, a)) return b; for(int j=19;~j;j--){ if(!is(t, par[t][a][j], b)) a = par[t][a][j]; } return par[t][a][0]; }; sort(p.begin(), p.end(), [&](int a, int b){ return tin[1][a] < tin[1][b]; }); for(int i=1;i<k;i++){ cout<<"? "<<p[i-1]<<" "<<p[i]<<endl; } cout<<"! "<<endl; for(int i=1;i<k;i++){ int dc, dd, da, db; cin >> dc >> dd >> da >> db; int lca = Lca(1, p[i-1], p[i]); d[1][lca] = d[1][p[i-1]] - da; d[1][p[i]] = d[1][lca] + db; d[0][p[i]] = d[0][p[i-1]] - dc + dd; } vector<ar<int, 2>> Q; for(int i=0;i<T;i++){ int a, b; cin >> a >> b; Q.push_back({a, b}); } for(auto [a, b] : Q){ for(int c=0;c<2;c++){ int lca = Lca(c, a, b); cout<<d[c][a] + d[c][b] - d[c][lca] * 2<<" "; } cout<<endl; } }
#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...