oj.uz

Submission #791546

# Submission time Handle Problem Language Result Execution time Memory
791546 2023-07-24T07:17:43 Z t6twotwo Prize (CEOI22_prize) C++17
10 / 100
 1798 ms 246052 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K, Q, T;
    cin >> N >> K >> Q >> T;
    vector<int> p(N);
    for (int &x : p) {
        cin >> x;
    }
    vector<vector<int>> adj(N);
    int root = -1;
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        if (p[i] == -1) {
            root = i;
        } else {
            p[i]--;
            adj[p[i]].push_back(i);
        }
    }
    vector<int> ch;
    auto choose = [&](auto f, int x) -> void {
        if (ch.size() < K) {
            ch.push_back(x);
        }
        for (int y : adj[x]) {
            f(f, y);
        }
    };
    choose(choose, root);
    for (int x : ch) {
        cout << x + 1 << " ";
    }
    cout << endl;
    vector<ll> w(N);
    for (int x : ch) {
        if (x != root) {
            cout << "? " << p[x] + 1 << " " << x + 1 << endl;
        }
    }
    cout << "!" << endl;
    for (int x : ch) {
        if (x != root) {
            cin >> w[x] >> w[x] >> w[x] >> w[x];
        }
    }
    vector<int> dep(N);
    vector par(N, vector<int>(19, -1));
    auto dfs = [&](auto dfs, int x) -> void {
        for (int i = 0; i < 18 && par[x][i] != -1; i++) {
            par[x][i + 1] = par[par[x][i]][i];
        }
        for (int y : adj[x]) {
            w[y] += w[x];
            par[y][0] = x;
            dep[y] = dep[x] + 1;
            dfs(dfs, y);
        }
    };
    dfs(dfs, root);
    auto lca = [&](int x, int y) {
        if (dep[x] < dep[y]) {
            swap(x, y);
        }
        for (int i = 0; i < 19; i++) {
            if ((dep[x] - dep[y]) >> i & 1) {
                x = par[x][i];
            }
        }
        if (x == y) {
            return x;
        }
        for (int i = 18; i >= 0; i--) {
            if (par[x][i] != par[y][i]) {
                x = par[x][i];
                y = par[y][i];
            }
        }
        return par[x][0];
    };
    vector<pair<int, int>> queries(T);
    for (int i = 0; i < T; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        queries[i] = {x, y};
    }
    for (auto [x, y] : queries) {
        cout << w[x] + w[y] - 2 * w[lca(x, y)] << " ";
        cout << w[x] + w[y] - 2 * w[lca(x, y)] << endl;
    }
    return 6/22;
}

Compilation message

Main.cpp: In instantiation of 'main()::<lambda(auto:23, int)> [with auto:23 = main()::<lambda(auto:23, int)>]':
Main.cpp:33:24:   required from here
Main.cpp:26:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |         if (ch.size() < K) {
      |             ~~~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1196 ms 123736 KB Output is correct
2 Correct 1173 ms 123828 KB Output is correct
3 Correct 498 ms 87936 KB Output is correct
4 Correct 513 ms 87788 KB Output is correct
5 Correct 481 ms 87876 KB Output is correct
6 Correct 874 ms 95124 KB Output is correct
7 Correct 947 ms 95108 KB Output is correct
8 Correct 978 ms 95092 KB Output is correct
9 Correct 555 ms 87900 KB Output is correct
10 Correct 473 ms 87928 KB Output is correct
11 Correct 513 ms 87752 KB Output is correct
12 Correct 500 ms 87844 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 824 ms 123792 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 721 ms 122944 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1733 ms 245732 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1798 ms 246052 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -