제출 #1235336

#제출 시각아이디문제언어결과실행 시간메모리
1235336spetrPrize (CEOI22_prize)C++20
0 / 100
245 ms75848 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; static const char endl_char = '\n'; // Interactive query: ask distances for nodes a and b // Reads four integers: d1( lca1, a ), d1( lca1, b ), d2( lca2, a ), d2( lca2, b ) tuple<ll,ll,ll,ll> ask(int a, int b) { cout << "? " << a << " " << b << "\n" << flush; ll d1a, d1b, d2a, d2b; if (!(cin >> d1a >> d1b >> d2a >> d2b)) { exit(0); // judge closed } return {d1a, d1b, d2a, d2b}; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, K, Q, T; cin >> N >> K >> Q >> T; vector<int> p1(N+1), p2(N+1); int root1 = -1, root2 = -1; for(int i = 1; i <= N; i++){ cin >> p1[i]; if(p1[i] == -1) root1 = i; } for(int i = 1; i <= N; i++){ cin >> p2[i]; if(p2[i] == -1) root2 = i; } // build adjacency of tree1 to select K connected nodes vector<vector<int>> adj1(N+1); for(int i = 1; i <= N; i++){ if(p1[i] != -1){ adj1[i].push_back(p1[i]); adj1[p1[i]].push_back(i); } } // BFS from root1, take first K nodes vector<int> subset; subset.reserve(K); vector<int> parent_in_sub(N+1, -1); vector<bool> used(N+1, false); queue<int> q; q.push(root1); used[root1] = true; subset.push_back(root1); while(!q.empty() && (int)subset.size() < K){ int u = q.front(); q.pop(); for(int v : adj1[u]){ if(!used[v]){ used[v] = true; parent_in_sub[v] = u; subset.push_back(v); q.push(v); if((int)subset.size() == K) break; } } } // 1) output chosen subset for(int i = 0; i < K; i++){ cout << subset[i] << (i+1 < K ? ' ' : '\n'); } cout << flush; // 2) ask K-1 queries: for each non-root in subset, ask (parent, node) // and compute the edge-weights in both trees. vector<vector<pair<int,ll>>> tree1(K), tree2(K); // map original label -> index in subset unordered_map<int,int> idx; idx.reserve(K*2); for(int i = 0; i < K; i++){ idx[subset[i]] = i; } for(int i = 1; i < K; i++){ int u = subset[i]; int par = parent_in_sub[u]; // ask distances auto [d1_par, d1_u, d2_par, d2_u] = ask(par, u); // weight for tree1 edge par-u: ll w1 = llabs(d1_u - d1_par); ll w2 = llabs(d2_u - d2_par); int iu = i, ip = idx[par]; tree1[ip].push_back({iu, w1}); tree1[iu].push_back({ip, w1}); tree2[ip].push_back({iu, w2}); tree2[iu].push_back({ip, w2}); } // signal end of queries cout << "!\n" << flush; // 3) preprocess LCA + dist for both trees on subset nodes auto build_lca = [&](vector<vector<pair<int,ll>>> &adj, vector<int>& depth, vector<ll>& dist, vector<vector<int>>& up) { int LOG = up.size(); int n = adj.size(); function<void(int,int)> dfs = [&](int u, int p){ for(auto [v, w]: adj[u]){ if(v == p) continue; depth[v] = depth[u] + 1; dist[v] = dist[u] + w; up[0][v] = u; for(int j = 1; j < LOG; j++){ up[j][v] = up[j-1][ up[j-1][v] ]; } dfs(v, u); } }; // root at index 0 depth[0] = 0; dist[0] = 0; for(int j = 0; j < LOG; j++) up[j][0] = 0; dfs(0, -1); }; int LOG = 1; while ((1<<LOG) <= K) LOG++; vector<int> depth1(K), depth2(K); vector<ll> dist1(K), dist2(K); vector<vector<int>> up1(LOG, vector<int>(K)), up2(LOG, vector<int>(K)); build_lca(tree1, depth1, dist1, up1); build_lca(tree2, depth2, dist2, up2); auto lca = [&](int u, int v, vector<int>& depth, vector<vector<int>>& up){ if(depth[u] < depth[v]) swap(u,v); int diff = depth[u] - depth[v]; for(int j = 0; j < LOG; j++){ if(diff & (1<<j)) u = up[j][u]; } if(u == v) return u; for(int j = LOG-1; j >= 0; j--){ if(up[j][u] != up[j][v]){ u = up[j][u]; v = up[j][v]; } } return up[0][u]; }; // 4) handle T host questions while(T--){ int pa, pb; cin >> pa >> pb; int ia = idx[pa], ib = idx[pb]; // dist in tree1 int c1 = lca(ia, ib, depth1, up1); ll ans1 = dist1[ia] + dist1[ib] - 2*dist1[c1]; // dist in tree2 int c2 = lca(ia, ib, depth2, up2); ll ans2 = dist2[ia] + dist2[ib] - 2*dist2[c2]; cout << ans1 << " " << ans2 << "\n"; } cout << flush; return 0; }
#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...