oj.uz

Submission #1112130

# Submission time Handle Problem Language Result Execution time Memory
1112130 2024-11-13T16:51:49 Z MisterReaper Prize (CEOI22_prize) C++17
100 / 100
 1730 ms 433484 KB 
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "../../debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1E6) + 5;
constexpr int LG = 20;

int N, K, Q, T;
int root[2], par[2][LG][max_N], tin[2][max_N], tout[2][max_N], timer;
std::vector<int> adj[2][max_N];

std::vector<int> vec;
void dfs(int tp, int v) {
    tin[tp][v] = timer++;
    if (vec.size() < K) {
        vec.emplace_back(v);
    }
    for (auto u : adj[tp][v]) {
        par[tp][0][u] = v;
        dfs(tp, u);
    }
    tout[tp][v] = timer;
}

bool is_in_subtree(int tp, int u, int v) {
    return tin[tp][v] <= tin[tp][u] && tout[tp][u] <= tout[tp][v];
}

int lca(int tp, int u, int v) {
    if (is_in_subtree(tp, u, v)) {
        return v;
    } else if (is_in_subtree(tp, v, u)) {
        return u;
    }
    for (int lg = LG - 1; lg >= 0; --lg) {
        if (!is_in_subtree(tp, v, par[tp][lg][u])) {
            u = par[tp][lg][u];
        }
    }
    return par[tp][0][u];
}

int dep[2][max_N], vis[2][max_N];
std::vector<std::pair<int, int>> hint[2][max_N];
void add_edge(int tp, int u, int v, int x) {
    hint[tp][v].emplace_back(u, x);
    hint[tp][u].emplace_back(v, -x);
}

void solve(int tp, int v) {
    vis[tp][v] = true;
    debug(tp, v, dep[tp][v]);
    for (auto[u, w] : hint[tp][v]) {
        if (vis[tp][u]) {
            if(dep[tp][u] != dep[tp][v] + w) {
                debug(tp, u, v, w, dep[tp][u], dep[tp][v]);
                assert(false);
            }
            continue;
        }
        dep[tp][u] = dep[tp][v] + w;
        solve(tp, u);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr); 

    std::cin >> N >> K >> Q >> T;

    for (int tp : {0, 1}) {
        for (int i = 0; i < N; ++i) {
            int P;
            std::cin >> P;
            if (P == -1) {
                root[tp] = i;
            } else {
                adj[tp][P - 1].emplace_back(i);
            }
        }
    }

    timer = 0;
    dfs(0, root[0]);
    timer = 0;
    dfs(1, root[1]);

    for (int tp : {0, 1}) {
        par[tp][0][root[tp]] = root[tp];
        for (int lg = 0; lg + 1 < LG; ++lg) {
            for (int i = 0; i < N; ++i) {
                par[tp][lg + 1][i] = par[tp][lg][par[tp][lg][i]];
            }
        }
    }

    std::sort(vec.begin(), vec.end(), [&](auto lhs, auto rhs) {
        return tin[1][lhs] < tin[1][rhs];
    });

    for (int i = 0; i < K; ++i) {
        std::cout << vec[i] + 1 << " \n"[i == K - 1];
    }
    std::cout.flush();

    for (int i = 0; i < K - 1; ++i) {
        std::cout << "? " << vec[i] + 1 << ' ' << vec[i + 1] + 1 << '\n';
    }
    std::cout << "!\n";
    std::cout.flush();

    for (int i = 0; i < K - 1; ++i) {
        int A, B, C, D;
        std::cin >> A >> B >> C >> D;
        int u = vec[i], v = vec[i + 1];
        int lca0 = lca(0, u, v);
        int lca1 = lca(1, u, v);
        add_edge(0, u, lca0, A);
        add_edge(0, v, lca0, B);
        add_edge(1, u, lca1, C);
        add_edge(1, v, lca1, D);
    }

    solve(0, vec[0]);
    solve(1, vec[0]);

    std::vector<std::pair<int, int>> ans(T);
    for (int i = 0; i < T; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        int lca0 = lca(0, A, B);
        int lca1 = lca(1, A, B);

        int ans0 = dep[0][A] + dep[0][B] - 2 * dep[0][lca0];
        int ans1 = dep[1][A] + dep[1][B] - 2 * dep[1][lca1];
        ans[i] = {ans0, ans1};
    }

    for (int i = 0; i < T; ++i) {
        std::cout << ans[i].first << ' ' << ans[i].second << '\n';
        std::cout.flush();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:21:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |     if (vec.size() < K) {
      |         ~~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 355980 KB Output is correct
2 Correct 788 ms 358408 KB Output is correct
3 Correct 683 ms 302576 KB Output is correct
4 Correct 743 ms 302224 KB Output is correct
5 Correct 683 ms 304636 KB Output is correct
6 Correct 878 ms 315048 KB Output is correct
7 Correct 795 ms 314424 KB Output is correct
8 Correct 748 ms 314072 KB Output is correct
9 Correct 793 ms 302456 KB Output is correct
10 Correct 717 ms 303984 KB Output is correct
11 Correct 618 ms 300976 KB Output is correct
12 Correct 674 ms 303884 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 359024 KB Output is correct
2 Correct 728 ms 354472 KB Output is correct
3 Correct 724 ms 302580 KB Output is correct
4 Correct 857 ms 304956 KB Output is correct
5 Correct 800 ms 303704 KB Output is correct
6 Correct 979 ms 313016 KB Output is correct
7 Correct 996 ms 316032 KB Output is correct
8 Correct 1002 ms 316320 KB Output is correct
9 Correct 840 ms 314120 KB Output is correct
10 Correct 1091 ms 314916 KB Output is correct
11 Correct 898 ms 311644 KB Output is correct
12 Correct 988 ms 314840 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 345988 KB Output is correct
2 Correct 570 ms 347480 KB Output is correct
3 Correct 425 ms 293160 KB Output is correct
4 Correct 366 ms 293216 KB Output is correct
5 Correct 369 ms 293368 KB Output is correct
6 Correct 467 ms 304672 KB Output is correct
7 Correct 398 ms 304684 KB Output is correct
8 Correct 450 ms 303432 KB Output is correct
9 Correct 460 ms 302636 KB Output is correct
10 Correct 369 ms 301356 KB Output is correct
11 Correct 429 ms 302444 KB Output is correct
12 Correct 506 ms 302368 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1326 ms 422000 KB Output is correct
2 Correct 1191 ms 421340 KB Output is correct
3 Correct 935 ms 313584 KB Output is correct
4 Correct 960 ms 313864 KB Output is correct
5 Correct 993 ms 313804 KB Output is correct
6 Correct 1365 ms 336116 KB Output is correct
7 Correct 1361 ms 337052 KB Output is correct
8 Correct 1314 ms 336476 KB Output is correct
9 Correct 1129 ms 332352 KB Output is correct
10 Correct 1183 ms 332508 KB Output is correct
11 Correct 1189 ms 332364 KB Output is correct
12 Correct 997 ms 332132 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1312 ms 433484 KB Output is correct
2 Correct 1394 ms 432600 KB Output is correct
3 Correct 1177 ms 322372 KB Output is correct
4 Correct 1309 ms 325900 KB Output is correct
5 Correct 1232 ms 321312 KB Output is correct
6 Correct 1730 ms 348780 KB Output is correct
7 Correct 1617 ms 344460 KB Output is correct
8 Correct 1582 ms 347284 KB Output is correct
9 Correct 1455 ms 342104 KB Output is correct
10 Correct 1516 ms 341016 KB Output is correct
11 Correct 1545 ms 341096 KB Output is correct
12 Correct 1545 ms 342936 KB Output is correct