Submission #1235336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235336		spetr	Prize (CEOI22_prize)	C++20	0 / 100	245 ms	75848 KiB

Main

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24