Submission #1187516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187516		user192837	Prize (CEOI22_prize)	C++17	10 / 100	3035 ms	349572 KiB

Main

#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long long ll;

const int N = 1e6 + 6;
vector <int> g[2][N];
ll checkpoint[2][N];
int st[2][20][N], d[2][N], taken[N], vis[N], root[2], cnt[N], qd;

void dfs(int x, int par) {
    d[qd][x] = d[qd][par] + 1, st[qd][0][x] = par;
    for (int i = 1; i < 20; i++)
        st[qd][i][x] = st[qd][i - 1][st[qd][i - 1][x]];
    for (int &y : g[qd][x])
        if (y != par)
            dfs(y, x);
}

int lca(int a, int b) {
    if (d[qd][a] > d[qd][b])
        swap(a, b);
    int i = 0, k = d[qd][b] - d[qd][a];
    while (k) {
        if (k & 1)
            b = st[qd][i][b];
        k >>= 1;
        i++;
    }
    if (a == b)
        return a;
    i = 19;
    while (i >= 0) {
        int na = st[qd][i][a], nb = st[qd][i][b];
        if (na != nb)
            a = na, b = nb;
        i--;
    }
    return st[qd][0][a];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    for (int i = 0; i < 2; i++) {
        for (int j = 1; j <= n; j++) {
            int p;
            cin >> p;
            if (~p)
                g[i][p].emplace_back(j), g[i][j].emplace_back(p);
            else
                root[i] = j;
            if (i == 1)
                cnt[max(0, p)] = 1;
        }
    }
    qd = 0; dfs(root[0], 0);
    qd = 1; dfs(root[1], 0);
    int rt = -1;
    for (int i = 1; i <= n; i++)
        if (cnt[i] == 0)
            rt = i;
    queue <int> que; que.push(rt);
    while (!que.empty()) {
        int x = que.front(); que.pop();
        vis[x] = 1;
        if (k > 0)
            k--, taken[x] = 1;
        for (int y : g[0][x])
            if (!vis[y])
                que.push(y);
    }
    int prnt = 0;
    for (int i = 1; i <= n; i++) {
        if (taken[i]) {
            if (prnt)
                cout << ' ';
            cout << i, prnt = 1;
        }
    }
    cout << '\n' << flush;
    for (int i = 1; i <= n; i++) {
        if (taken[i] && i != rt) {
            cout << "? " << rt << ' ' << i << '\n';
            q--;
        }
    }
    cout << "!\n" << flush;
    for (int i = 1; i <= n; i++) {
        if (taken[i] && i != rt) {
            int y = i;
            vector <ll> res(4);
            for (ll &j : res)
                cin >> j;
            qd = 0; int lc0 = lca(rt, y);
            qd = 1; int lc1 = lca(rt, y);
            if (lc0 == rt)
                checkpoint[0][y] = res[1];
            else
                checkpoint[0][lc0] = res[0], checkpoint[0][y] = res[0] + res[1];
            checkpoint[1][lc1] = res[2];
            checkpoint[1][y] = res[2] + res[3];
        }
    }
    qd = 0; dfs(rt, 0);
    qd = 1; dfs(rt, 0);
    vector <ar <int, 2>> qrs(t);
    for (auto &i : qrs)
        cin >> i[0] >> i[1];
    for (auto i : qrs) {
        int a = i[0], b = i[1];
        qd = 0; cout << checkpoint[0][a] + checkpoint[0][b] - 2 * checkpoint[0][lca(a, b)] << ' ';
        qd = 1; cout << checkpoint[1][a] + checkpoint[1][b] - 2 * checkpoint[1][lca(a, b)] << '\n';
    }
    cout << flush;
}

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