oj.uz

Submission #957423

# Submission time Handle Problem Language Result Execution time Memory
957423 2024-04-03T16:40:54 Z Lukap Prize (CEOI22_prize) C++14
100 / 100
 2827 ms 411024 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1367 ms 270904 KB Output is correct
2 Correct 1350 ms 273520 KB Output is correct
3 Correct 899 ms 233316 KB Output is correct
4 Correct 898 ms 232656 KB Output is correct
5 Correct 962 ms 235776 KB Output is correct
6 Correct 1275 ms 242884 KB Output is correct
7 Correct 1330 ms 241728 KB Output is correct
8 Correct 1209 ms 241572 KB Output is correct
9 Correct 863 ms 233088 KB Output is correct
10 Correct 931 ms 234384 KB Output is correct
11 Correct 871 ms 231656 KB Output is correct
12 Correct 961 ms 234468 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1537 ms 273432 KB Output is correct
2 Correct 1358 ms 269100 KB Output is correct
3 Correct 967 ms 233268 KB Output is correct
4 Correct 1044 ms 235844 KB Output is correct
5 Correct 946 ms 234708 KB Output is correct
6 Correct 1421 ms 240892 KB Output is correct
7 Correct 1551 ms 243712 KB Output is correct
8 Correct 1569 ms 244104 KB Output is correct
9 Correct 1234 ms 242020 KB Output is correct
10 Correct 1294 ms 242712 KB Output is correct
11 Correct 1188 ms 239416 KB Output is correct
12 Correct 1297 ms 242452 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 894 ms 263536 KB Output is correct
2 Correct 858 ms 262216 KB Output is correct
3 Correct 587 ms 223404 KB Output is correct
4 Correct 572 ms 224040 KB Output is correct
5 Correct 582 ms 223892 KB Output is correct
6 Correct 795 ms 232304 KB Output is correct
7 Correct 754 ms 232516 KB Output is correct
8 Correct 741 ms 233732 KB Output is correct
9 Correct 691 ms 230348 KB Output is correct
10 Correct 674 ms 231552 KB Output is correct
11 Correct 682 ms 230180 KB Output is correct
12 Correct 715 ms 230216 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2330 ms 398792 KB Output is correct
2 Correct 2138 ms 399088 KB Output is correct
3 Correct 1419 ms 322348 KB Output is correct
4 Correct 1398 ms 322580 KB Output is correct
5 Correct 1421 ms 322032 KB Output is correct
6 Correct 1933 ms 339236 KB Output is correct
7 Correct 1953 ms 339364 KB Output is correct
8 Correct 1952 ms 339056 KB Output is correct
9 Correct 1716 ms 335172 KB Output is correct
10 Correct 1779 ms 335480 KB Output is correct
11 Correct 1766 ms 335200 KB Output is correct
12 Correct 1787 ms 335640 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2768 ms 411024 KB Output is correct
2 Correct 2827 ms 409996 KB Output is correct
3 Correct 1722 ms 331424 KB Output is correct
4 Correct 1794 ms 334512 KB Output is correct
5 Correct 1643 ms 330208 KB Output is correct
6 Correct 2585 ms 351336 KB Output is correct
7 Correct 2509 ms 347568 KB Output is correct
8 Correct 2573 ms 349852 KB Output is correct
9 Correct 2110 ms 344708 KB Output is correct
10 Correct 2079 ms 343952 KB Output is correct
11 Correct 2154 ms 343724 KB Output is correct
12 Correct 2148 ms 346172 KB Output is correct