Submission #652553

#TimeUsernameProblemLanguageResultExecution timeMemory
652553bluePrize (CEOI22_prize)C++17
0 / 100
1074 ms182336 KiB
#include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using pii = pair<int, int>; using vpii = vector<pii>; using pll = pair<ll, ll>; using vpll = vector<pll>; #define sz(x) int(x.size()) int N, K, Q, T; const int mx = 500'000; const int lg = 4; int p[2][1+mx]; vi children[2][1+mx]; int rt[2]; vvi dfsorder(2, vi(1, 0)); vvi dfsind(2, vi(1+mx, 0)); vi ct(2, 0); vvi depth(2, vi(1+mx, 0)); int anc[2][1 + mx][1 + lg]; void dfs(int t, int u) { ct[t]++; dfsind[t][u] = ct[t]; dfsorder[t].push_back(u); for(int v : children[t][u]) { depth[t][v] = depth[t][u] + 1; dfs(t, v); } } int lca(int t, int u, int v) { if(depth[t][u] > depth[t][v]) swap(u, v); for(int e = lg; e >= 0; e--) { if((1 << e) & (depth[t][v] - depth[t][u])) v = anc[t][v][e]; } if(u == v) return u; for(int e = lg; e >= 0; e--) { if(anc[t][u][e] != anc[t][v][e]) { u = anc[t][u][e]; v = anc[t][v][e]; } } return anc[t][u][0]; } vi lst[2]; int gt; vpii edge[2][1 + mx]; int distrt[2][1 + mx]; int main() { cin >> N >> K >> Q >> T; for(int t = 0; t < 2; t++) { for(int i = 1; i <= N; i++) { cin >> p[t][i]; } rt[t] = 1; while(p[t][rt[t]] != -1) rt[t]++; for(int i = 1; i <= N; i++) { if(i == rt[t]) continue; children[t][p[t][i]].push_back(i); } dfs(t, rt[t]); } for(int i = 1; i <= K; i++) cout << i << ' '; cout << '\n'; cout.flush(); for(int t = 0; t <= 1; t++) { for(int i = 1; i <= K; i++) lst[t].push_back(i); gt = t; sort(lst[t].begin(), lst[t].end(), [] (int u, int v) { return dfsind[gt][u] < dfsind[gt][v]; }); for(int i = 0; i+1 < K; i++) { cout << "? " << lst[t][i] << ' ' << lst[t][i+1] << '\n'; } } cout << "!\n"; cout.flush(); for(int t = 0; t <= 1; t++) { for(int i = 1; i <= N; i++) anc[t][i][0] = p[t][i]; anc[t][rt[t]][0] = rt[t]; for(int e = 1; e <= lg; e++) for(int i = 1; i <= N; i++) anc[t][i][e] = anc[t][ anc[t][i][e-1] ][e-1]; } for(int t = 0; t <= 1; t++) { vi lcv, dav, dbv; for(int i = 0; i+1 < K; i++) { int jnk, da, db; if(t == 0) { cin >> da >> db >> jnk >> jnk; } else { cin >> jnk >> jnk >> da >> db; } int lc = lca(t, lst[t][i], lst[t][i+1]); lcv.push_back(lc); dav.push_back(da); dbv.push_back(db); edge[t][lc].push_back({lst[t][i], da}); edge[t][lc].push_back({lst[t][i+1], db}); // cerr << t << ' ' << lc << " -> " << lst[t][i] << ' ' << da << " , " << lst[t][i+1] << ' ' << db << '\n'; // lst[t].push_back(lc); } for(int i = 1; i < K-1; i++) { if(lcv[i] == lcv[i-1]) continue; // cerr << i << " : " << lcv[i-1] << ' ' << lcv[i] << " a \n"; // cerr << dbv[i-1] << ' ' << dav[i] << '\n'; if(dbv[i-1] >= dav[i]) edge[t][lcv[i-1]].push_back({lcv[i], dbv[i-1] - dav[i]}); else edge[t][lcv[i]].push_back({lcv[i-1], dav[i] - dbv[i-1]}); } // cerr << "read\n"; // gt = t; // sort(lst[t].begin(), lst[t].end(), [] (int u, int v) // { // return dfsind[gt][u] < dfsind[gt][v]; // }); for(int i = 1; i <= N; i++) distrt[t][i] = 0; for(int u : dfsorder[t]) { if(u == 0) continue; for(pii vp : edge[t][u]) { int v = vp.first; int w = vp.second; distrt[t][v] = max(distrt[t][v], distrt[t][u] + w); } } } // for(int t = 0; t <= 1; t++) // { // for(int i = 1; i <= N; i++) // cerr << distrt[t][i] << ' '; // cerr << '\n'; // } for(int t = 1; t <= T; t++) { int p, q; cin >> p >> q; int l0 = lca(0, p, q); int l1 = lca(1, p, q); // cerr << l0 << " | " << l1 << '\n'; // cerr << distrt[0][p] << ' ' << distrt[0][q] << ' ' << distrt[0][l0] << '\n'; ll ans0 = distrt[0][p] + distrt[0][q] - 2*distrt[0][l0]; ll ans1 = distrt[1][p] + distrt[1][q] - 2*distrt[1][l1]; cout << ans0 << ' ' << ans1 << '\n'; } cout.flush(); }
#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...