oj.uz

Submission #1112136

# Submission time Handle Problem Language Result Execution time Memory
1112136 2024-11-13T16:55:05 Z MisterReaper Prize (CEOI22_prize) C++17
100 / 100
 2380 ms 433432 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::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 933 ms 355808 KB Output is correct
2 Correct 848 ms 358256 KB Output is correct
3 Correct 964 ms 302684 KB Output is correct
4 Correct 866 ms 302200 KB Output is correct
5 Correct 910 ms 304468 KB Output is correct
6 Correct 1099 ms 314836 KB Output is correct
7 Correct 1006 ms 314652 KB Output is correct
8 Correct 1080 ms 314128 KB Output is correct
9 Correct 883 ms 302420 KB Output is correct
10 Correct 947 ms 303764 KB Output is correct
11 Correct 918 ms 301256 KB Output is correct
12 Correct 941 ms 304072 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 358928 KB Output is correct
2 Correct 1089 ms 354392 KB Output is correct
3 Correct 958 ms 302448 KB Output is correct
4 Correct 1148 ms 305080 KB Output is correct
5 Correct 1002 ms 303932 KB Output is correct
6 Correct 1206 ms 312752 KB Output is correct
7 Correct 1293 ms 315840 KB Output is correct
8 Correct 1314 ms 316236 KB Output is correct
9 Correct 1313 ms 314324 KB Output is correct
10 Correct 1262 ms 314876 KB Output is correct
11 Correct 1080 ms 311752 KB Output is correct
12 Correct 1301 ms 314668 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 345932 KB Output is correct
2 Correct 910 ms 347264 KB Output is correct
3 Correct 599 ms 293108 KB Output is correct
4 Correct 648 ms 293132 KB Output is correct
5 Correct 673 ms 293332 KB Output is correct
6 Correct 709 ms 304660 KB Output is correct
7 Correct 735 ms 304528 KB Output is correct
8 Correct 739 ms 303604 KB Output is correct
9 Correct 660 ms 302468 KB Output is correct
10 Correct 664 ms 301320 KB Output is correct
11 Correct 636 ms 302504 KB Output is correct
12 Correct 621 ms 302356 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 421876 KB Output is correct
2 Correct 1788 ms 421160 KB Output is correct
3 Correct 1362 ms 313772 KB Output is correct
4 Correct 1405 ms 313896 KB Output is correct
5 Correct 1418 ms 313968 KB Output is correct
6 Correct 1534 ms 336052 KB Output is correct
7 Correct 1693 ms 337000 KB Output is correct
8 Correct 1710 ms 336144 KB Output is correct
9 Correct 1541 ms 332368 KB Output is correct
10 Correct 1679 ms 332552 KB Output is correct
11 Correct 1556 ms 332296 KB Output is correct
12 Correct 1514 ms 331920 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1930 ms 433432 KB Output is correct
2 Correct 1826 ms 432780 KB Output is correct
3 Correct 1723 ms 322400 KB Output is correct
4 Correct 1842 ms 326088 KB Output is correct
5 Correct 1671 ms 321408 KB Output is correct
6 Correct 2380 ms 348792 KB Output is correct
7 Correct 2137 ms 344768 KB Output is correct
8 Correct 2185 ms 347236 KB Output is correct
9 Correct 2012 ms 342076 KB Output is correct
10 Correct 2004 ms 340820 KB Output is correct
11 Correct 2029 ms 341500 KB Output is correct
12 Correct 1889 ms 343080 KB Output is correct