oj.uz

Submission #957418

# Submission time Handle Problem Language Result Execution time Memory
957418 2024-04-03T16:33:14 Z Lukap Prize (CEOI22_prize) C++14
0 / 100
 2183 ms 409536 KB 
#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));
    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);
            }
        }
    }

    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);
    printf("\n"); fflush(stdout);

    for (int i = 0; i < k - 1; i++) printf("? %d %d\n", v[i], v[i + 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);

    for (int i = 0; i < t; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        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:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d%d%d%d", &n, &k, &q, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~
Main.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 271912 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1271 ms 274428 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 864 ms 264964 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1857 ms 399264 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2183 ms 409536 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -