Submission #1112136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112136		MisterReaper	Prize (CEOI22_prize)	C++17	100 / 100	2380 ms	433432 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24