oj.uz

Submission #1112137

# Submission time Handle Problem Language Result Execution time Memory
1112137 2024-11-13T16:55:45 Z MisterReaper Prize (CEOI22_prize) C++17
100 / 100
 1845 ms 433556 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];
    });

    std::cout << vec[0] + 1;
    for (int i = 1; i < K; ++i) {
        std::cout << ' ' << vec[i] + 1;
    }
    std::cout << std::endl;

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

    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 << std::endl;
    }

    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 721 ms 355944 KB Output is correct
2 Correct 827 ms 358616 KB Output is correct
3 Correct 758 ms 302576 KB Output is correct
4 Correct 739 ms 302092 KB Output is correct
5 Correct 777 ms 304632 KB Output is correct
6 Correct 879 ms 314920 KB Output is correct
7 Correct 929 ms 314424 KB Output is correct
8 Correct 900 ms 314152 KB Output is correct
9 Correct 762 ms 302668 KB Output is correct
10 Correct 822 ms 303716 KB Output is correct
11 Correct 762 ms 301028 KB Output is correct
12 Correct 817 ms 303728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 358788 KB Output is correct
2 Correct 719 ms 354368 KB Output is correct
3 Correct 794 ms 302936 KB Output is correct
4 Correct 905 ms 305020 KB Output is correct
5 Correct 862 ms 303568 KB Output is correct
6 Correct 989 ms 313012 KB Output is correct
7 Correct 1139 ms 315840 KB Output is correct
8 Correct 1120 ms 316080 KB Output is correct
9 Correct 918 ms 314132 KB Output is correct
10 Correct 1014 ms 314912 KB Output is correct
11 Correct 919 ms 311924 KB Output is correct
12 Correct 1078 ms 314700 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 345924 KB Output is correct
2 Correct 639 ms 347120 KB Output is correct
3 Correct 466 ms 293316 KB Output is correct
4 Correct 436 ms 293240 KB Output is correct
5 Correct 385 ms 293276 KB Output is correct
6 Correct 523 ms 304676 KB Output is correct
7 Correct 578 ms 304744 KB Output is correct
8 Correct 577 ms 303504 KB Output is correct
9 Correct 440 ms 302624 KB Output is correct
10 Correct 496 ms 301348 KB Output is correct
11 Correct 479 ms 302624 KB Output is correct
12 Correct 477 ms 302548 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1363 ms 421756 KB Output is correct
2 Correct 1238 ms 421376 KB Output is correct
3 Correct 939 ms 313808 KB Output is correct
4 Correct 986 ms 313896 KB Output is correct
5 Correct 981 ms 313800 KB Output is correct
6 Correct 1239 ms 336072 KB Output is correct
7 Correct 1349 ms 337492 KB Output is correct
8 Correct 1266 ms 336176 KB Output is correct
9 Correct 1249 ms 332504 KB Output is correct
10 Correct 1221 ms 332836 KB Output is correct
11 Correct 1257 ms 332904 KB Output is correct
12 Correct 1240 ms 332288 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 433556 KB Output is correct
2 Correct 1438 ms 432808 KB Output is correct
3 Correct 1403 ms 322432 KB Output is correct
4 Correct 1446 ms 326028 KB Output is correct
5 Correct 1351 ms 321328 KB Output is correct
6 Correct 1845 ms 349256 KB Output is correct
7 Correct 1509 ms 344608 KB Output is correct
8 Correct 1621 ms 347248 KB Output is correct
9 Correct 1632 ms 342312 KB Output is correct
10 Correct 1464 ms 341016 KB Output is correct
11 Correct 1497 ms 341088 KB Output is correct
12 Correct 1466 ms 343112 KB Output is correct