Submission #957409

#	Time	Username	Problem	Language	Result	Execution time	Memory
957409		Lukap	Prize (CEOI22_prize)	C++14	0 / 100	2163 ms	409204 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 500;
const int LOG = 21;

int n, k, q, t;
int rod[2][MAXN][LOG], d[2][MAXN], dt[2][MAXN], tim, bio[2][MAXN], rj[2][MAXN];
vector<int> djeca[2][MAXN], v;
vector<pair<int, int> > susjedi[2][MAXN];

void dfs (int x, int br, int g) {
    d[g][x] = br;
    dt[g][x] = tim++;
    for (auto nx: djeca[g][x]) dfs (nx, br + 1, g);
}

bool cmp (int x, int y) {
    return dt[1][x] < dt[1][y];
}

int lca (int g, int x, int y) {
    if (d[g][x] > d[g][y]) swap (x, y);

    for (int i = LOG - 1; i >= 0; i--) {
        if (d[g][rod[g][y][i]] >= d[g][x]) y = rod[g][y][i];
    }

    if (x == y) return x;

    for (int i = LOG - 1; i >= 0; i--) {
        if (rod[g][x][i] != rod[g][y][i]) {
            x = rod[g][x][i];
            y = rod[g][y][i];
        }
    }

    return rod[g][x][0];
}

void dfs2 (int x, int g) {
    bio[g][x] = 0;
    for (auto it: susjedi[g][x]) {
        int nx = it.first;
        if (bio[g][nx] != -1) continue;
        rj[g][nx] = rj[g][x] + it.second;
        dfs2 (nx, g);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    memset (bio, -1, sizeof (bio));
    cin >> n >> k >> q >> t;

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;
            if (a == -1) rod[i][j][0] = j;
            else {
                a--;
                rod[i][j][0] = a;
                djeca[i][a].push_back (j);
            }
        }
    }

    for (int i = 0; i < 2; i++) {
        for (int j = 1; j < LOG; j++) {
            for (int l = 0; l < n; l++) rod[i][l][j] = rod[i][rod[i][l][j - 1]][j - 1];
        }
    }

    for (int i = 0; i < n; i++) {
        if (rod[0][i][0] == i) {
            tim = 0;
            dfs (i, 0, 0);
        }
        if (rod[1][i][0] == i) {
            tim = 0;
            dfs (i, 0, 1);
        }
    }

    for (int i = 0; i < n; i++) {
        if (dt[0][i] < k) v.push_back (i);
    }
    sort (v.begin (), v.end (), cmp);

    for (auto it: v) cout << it + 1 << ' ';
    cout << endl;

    for (int i = 0; i < k - 1; i++) cout << "? " << v[i] + 1 << ' ' << v[i + 1] + 1 << endl;
    cout << '!' << endl;

    for (int i = 0; i < k - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int x = v[i], y = v[i + 1];
        int lca0 = lca (0, x, y), lca1 = lca (1, x, y);

        susjedi[0][lca0].push_back ({x, a});
        susjedi[0][x].push_back ({lca0, -a});
        susjedi[0][lca0].push_back ({y, b});
        susjedi[0][y].push_back ({lca0, -b});

        susjedi[1][lca1].push_back ({x, c});
        susjedi[1][x].push_back ({lca1, -c});
        susjedi[1][lca1].push_back ({y, d});
        susjedi[1][y].push_back ({lca1, -d});
    }
    dfs2 (v[0], 0);
    dfs2 (v[0], 1);

    for (int i = 0; i < t; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        int lca0 = lca (0, a, b), lca1 = lca (1, a, b);

        if (i == t / 2) return 0;

        cout << rj[0][a] + rj[0][b] - 2 * rj[0][lca0] << ' ' << rj[1][a] + rj[1][b] - 2 * rj[1][lca1] << endl;
    }

    return 0;
}

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