Submission #1235341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235341		spetr	Prize (CEOI22_prize)	C++20	0 / 100	3587 ms	1071076 KiB

Main

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

const int MAXN = 1000000;
int n, k, q, t;
int p1[MAXN], p2[MAXN];
vector<int> tree1[MAXN], tree2[MAXN];

int dfn[MAXN], inv_dfn[MAXN], dfc;
int sz[MAXN], parent1[MAXN], depth1[MAXN], heavy[MAXN];
int head1[MAXN];

ll dist1[MAXN];
ll dis_query[MAXN];

// HLD on tree1
int dfs_sz(int u) {
    sz[u] = 1;
    int maxsz = 0;
    for (int v : tree1[u]) {
        depth1[v] = depth1[u] + 1;
        parent1[v] = u;
        ll w = 0; // we don't know weights here
        dist1[v] = dist1[u] + w;
        int vsz = dfs_sz(v);
        sz[u] += vsz;
        if (vsz > maxsz) {
            maxsz = vsz;
            heavy[u] = v;
        }
    }
    return sz[u];
}

void dfs_hld(int u, int h) {
    head1[u] = h;
    dfn[u] = dfc;
    inv_dfn[dfc++] = u;
    if (heavy[u] != -1) dfs_hld(heavy[u], h);
    for (int v : tree1[u]) if (v != heavy[u]) {
        dfs_hld(v, v);
    }
}

int lca1(int u, int v) {
    while (head1[u] != head1[v]) {
        if (depth1[head1[u]] > depth1[head1[v]]) u = parent1[head1[u]];
        else v = parent1[head1[v]];
    }
    return depth1[u] < depth1[v] ? u : v;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k >> q >> t;
    int root = -1;
    for(int i = 0; i < n; i++){
        cin >> p1[i];
        if(p1[i] == -1) root = i;
        else tree1[p1[i]].push_back(i);
    }
    for(int i = 0; i < n; i++){
        cin >> p2[i];
        if(p2[i] != -1) tree2[p2[i]].push_back(i);
    }
    // init
    fill(heavy, heavy+n, -1);
    parent1[root] = root;
    depth1[root] = 0;
    dist1[root] = 0;
    dfs_sz(root);
    dfs_hld(root, root);

    // choose first k by dfn order
    vector<int> subset(k);
    for(int i = 0; i < k; i++) subset[i] = inv_dfn[i];

    // output subset
    for(int i = 0; i < k; i++) cout << subset[i]+1 << (i+1<k?' ':'\n');
    // queries for each except root
    for(int i = 1; i < k; i++) {
        cout << "? " << subset[0]+1 << " " << subset[i]+1 << "\n";
    }
    cout << "!\n" << flush;

    // read q responses: format d1(root,a), d1(root,a), d2(root,a), d2(root,a)
    for(int i = 1; i < k; i++){
        ll d1l, d1a, d2l, d2a;
        cin >> d1l >> d1a >> d2l >> d2a;
        dis_query[ subset[i] ] = d1a;
        // store second tree same for simplicity
        dis_query[ subset[i]+n ] = d2a;
    }
    dis_query[ subset[0] ] = 0;
    dis_query[ subset[0]+n ] = 0;

    // answer t queries
    while(t--) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        // tree1 distance
        int w = lca1(u, v);
        ll d1 = dis_query[u] + dis_query[v] - 2*dis_query[w];
        // tree2 uses same lca
        ll d2 = dis_query[u+n] + dis_query[v+n] - 2*dis_query[w+n];
        cout << d1 << " " << d2 << '\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