Submission #957423

#	Time	Username	Problem	Language	Result	Execution time	Memory
957423		Lukap	Prize (CEOI22_prize)	C++14	100 / 100	2827 ms	411024 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;
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 () {
    scanf("%d%d%d%d", &n, &k, &q, &t);

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            int a;
            scanf("%d", &a);
            if (a == -1) rod[i][j][0] = j;
            else {
                a--;
                rod[i][j][0] = a;
                djeca[i][a].push_back (j);
            }
            bio[i][j] = -1;
        }
    }

    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) printf("%d ", it + 1);
    printf("\n"); fflush(stdout);

    for (int i = 0; i < k - 1; i++) printf("? %d %d\n", v[i] + 1, v[i + 1] + 1);
    printf("!\n"); fflush(stdout);

    for (int i = 0; i < k - 1; i++) {
        int a, b, c, d;
        scanf("%d %d %d %d", &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);

    vector<pair<int, int> > smrt;
    for (int i = 0; i < t; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        smrt.push_back({a, b});
    }

    for (auto it: smrt) {
        int a, b;
        a = it.first, b = it.second;
        a--;b--;
        int lca0 = lca (0, a, b), lca1 = lca (1, a, b);

        printf("%d ", rj[0][a] + rj[0][b] - 2 * rj[0][lca0]);
        printf("%d\n", rj[1][a] + rj[1][b] - 2 * rj[1][lca1]);
    }
    fflush(stdout);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d%d%d", &n, &k, &q, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~
Main.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %d %d %d", &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

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