Submission #1235338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235338		spetr	Prize (CEOI22_prize)	C++20	0 / 100	341 ms	108200 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    // Build adjacency for first tree
    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 to pick K connected nodes including root
    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() && subset.size() < (size_t)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(subset.size() == (size_t)K) break;
            }
        }
    }

    // Output chosen subset
    for(int i = 0; i < K; i++) cout << subset[i] << (i+1<K?' ':'\n');
    cout << flush;

    // Prepare queries for edge weights
    vector<pair<int,int>> queries;
    queries.reserve(K-1);
    for(int i = 1; i < K; i++){
        int u = subset[i];
        int par = parent_in_sub[u];
        queries.emplace_back(par, u);
    }
    // Ask all queries
    for(auto &pr: queries){
        cout << "? " << pr.first << " " << pr.second << "\n";
    }
    cout << "!\n" << flush;

    // Read all responses and build weighted subtrees
    unordered_map<int,int> idx;
    idx.reserve(K*2);
    for(int i = 0; i < K; i++) idx[subset[i]] = i;

    vector<vector<pair<int,ll>>> tree1(K), tree2(K);
    for(auto &pr: queries){
        ll d1a, d1b, d2a, d2b;
        cin >> d1a >> d1b >> d2a >> d2b;
        int u = pr.second;
        int par = pr.first;
        ll w1 = llabs(d1b - d1a);
        ll w2 = llabs(d2b - d2a);
        int iu = idx[u], ip = idx[par];
        tree1[ip].emplace_back(iu, w1);
        tree1[iu].emplace_back(ip, w1);
        tree2[ip].emplace_back(iu, w2);
        tree2[iu].emplace_back(ip, w2);
    }

    // Preprocess LCA+dist
    int LOG = 1;
    while((1<<LOG) <= K) LOG++;
    vector<vector<int>> up1(LOG, vector<int>(K)), up2(LOG, vector<int>(K));
    vector<int> depth1(K), depth2(K);
    vector<ll> dist1(K), dist2(K);
    function<void(int,int)> dfs1 = [&](int u, int p){
        for(auto &e: tree1[u]){
            int v = e.first; ll w = e.second;
            if(v == p) continue;
            depth1[v] = depth1[u]+1;
            dist1[v] = dist1[u]+w;
            up1[0][v] = u;
            for(int j=1;j<LOG;j++) up1[j][v] = up1[j-1][ up1[j-1][v] ];
            dfs1(v, u);
        }
    };
    function<void(int,int)> dfs2 = [&](int u, int p){
        for(auto &e: tree2[u]){
            int v = e.first; ll w = e.second;
            if(v == p) continue;
            depth2[v] = depth2[u]+1;
            dist2[v] = dist2[u]+w;
            up2[0][v] = u;
            for(int j=1;j<LOG;j++) up2[j][v] = up2[j-1][ up2[j-1][v] ];
            dfs2(v, u);
        }
    };
    // root at subset[0] -> index 0
    for(int j=0;j<LOG;j++){ up1[j][0]=up2[j][0]=0; }
    depth1[0]=depth2[0]=0;
    dist1[0]=dist2[0]=0;
    dfs1(0, -1);
    dfs2(0, -1);

    auto get_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>>j &1) 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];
    };

    // Answer T host queries
    while(T--){
        int pa, pb;
        cin >> pa >> pb;
        int ia = idx[pa], ib = idx[pb];
        int c1 = get_lca(ia, ib, depth1, up1);
        ll ans1 = dist1[ia] + dist1[ib] - 2*dist1[c1];
        int c2 = get_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