oj.uz

Submission #726044

# Submission time Handle Problem Language Result Execution time Memory
726044 2023-04-18T11:06:37 Z tengiz05 Prize (CEOI22_prize) C++17
59 / 100
 2648 ms 380532 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E6 + 5;

struct Tree {
    std::vector<int> adj[N];
    int up[N][20];
    int in[N], out[N];
    int timeStamp = 0;
    void dfs(int u, int p) {
        in[u] = timeStamp++;
        up[u][0] = p;
        for (int i = 1; i < 20; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (int v : adj[u]) {
            dfs(v, u);
        }
        out[u] = timeStamp;
    }
    bool is(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    int lca(int u, int v) {
        if (is(u, v)) return u;
        if (is(v, u)) return v;
        for (int i = 19; i >= 0; i--) {
            if (!is(up[u][i], v)) {
                u = up[u][i];
            }
        }
        return up[u][0];
    }
    std::vector<std::pair<int, int>> e[N];
    int sum[N];
    bool vis[N];
    void fill(int u) {
        vis[u] = true;
        for (auto [v, w] : e[u]) {
            if (vis[v]) continue;
            sum[v] = sum[u] + w;
            fill(v);
        }
    }
} t1, t2;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k, q, T;
    std::cin >> n >> k >> q >> T;
    
    int r1 = -1, r2 = -1;
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> p;
        if (p == -1) r1 = i;
        else {
            p--;
            t1.adj[p].push_back(i);
        }
    }
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> p;
        if (p == -1) r2 = i;
        else {
            p--;
            t2.adj[p].push_back(i);
        }
    }
    t1.dfs(r1, r1);
    t2.dfs(r2, r2);
    
    std::vector<int> f;
    for (int i = 0; i < n; i++) {
        if (t1.in[i] < k) {
            f.push_back(i);
        }
    }
    if (t1.in[r2] >= k) {
        f.pop_back();
        f.push_back(r2);
    }
    
    for (int i = 0; i < k; i++) {
        std::cout << f[i] + 1 << ' ';
    }
    std::cout << '\n';
    std::cout.flush();
    
    std::sort(f.begin(), f.end(), [&](int i, int j) {
        return t2.in[i] < t2.in[j];
    });
    for (int i = 0; i < k - 1; i++) {
        std::cout << "? " << f[i] + 1 << ' ' << f[i + 1] + 1 << '\n';
    }
    std::cout << "!" << '\n';
    std::cout.flush();
    
    for (int i = 0; i < k - 1; i++) {
        int a = f[i];
        int b = f[i + 1];
        int l = t1.lca(a, b);
        int c1, c2;
        std::cin >> c1 >> c2;
        t1.e[a].emplace_back(l, -c1);
        t1.e[l].emplace_back(a, c1);
        t1.e[b].emplace_back(l, -c2);
        t1.e[l].emplace_back(b, c2);
        l = t2.lca(a, b);
        std::cin >> c1 >> c2;
        t2.e[a].emplace_back(l, -c1);
        t2.e[l].emplace_back(a, c1);
        t2.e[b].emplace_back(l, -c2);
        t2.e[l].emplace_back(b, c2);
    }
    
    t1.fill(r1);
    t2.fill(r2);
    
    std::vector<std::pair<int, int>> queries(T);
    for (auto &[a, b] : queries) {
        std::cin >> a >> b;
        a--;
        b--;
    }
    
    for (auto [a, b] : queries) {
        int l = t1.lca(a, b);
        std::cout << t1.sum[a] + t1.sum[b] - 2 * t1.sum[l] << ' ';
        l = t2.lca(a, b);
        std::cout << t2.sum[a] + t2.sum[b] - 2 * t2.sum[l] << '\n';
    }
    std::cout.flush();
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1161 ms 239480 KB Output is correct
2 Correct 1322 ms 242196 KB Output is correct
3 Correct 930 ms 209660 KB Output is correct
4 Correct 895 ms 209448 KB Output is correct
5 Correct 1040 ms 211704 KB Output is correct
6 Correct 1354 ms 217596 KB Output is correct
7 Correct 1319 ms 217496 KB Output is correct
8 Correct 1266 ms 216884 KB Output is correct
9 Correct 891 ms 209460 KB Output is correct
10 Correct 1018 ms 211120 KB Output is correct
11 Correct 927 ms 208212 KB Output is correct
12 Correct 938 ms 210832 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 242268 KB Output is correct
2 Correct 1131 ms 238300 KB Output is correct
3 Correct 1014 ms 209704 KB Output is correct
4 Correct 1035 ms 212096 KB Output is correct
5 Correct 989 ms 210496 KB Output is correct
6 Correct 1340 ms 215656 KB Output is correct
7 Correct 1449 ms 218524 KB Output is correct
8 Correct 1458 ms 219012 KB Output is correct
9 Correct 1222 ms 217096 KB Output is correct
10 Correct 1283 ms 217588 KB Output is correct
11 Correct 1263 ms 214288 KB Output is correct
12 Correct 1266 ms 217384 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 229992 KB Output is correct
2 Correct 995 ms 229988 KB Output is correct
3 Correct 692 ms 199408 KB Output is correct
4 Correct 709 ms 199552 KB Output is correct
5 Correct 779 ms 199532 KB Output is correct
6 Correct 1240 ms 206544 KB Output is correct
7 Runtime error 845 ms 206484 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2189 ms 368292 KB Output is correct
2 Correct 2077 ms 368468 KB Output is correct
3 Runtime error 1336 ms 307600 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2329 ms 380532 KB Output is correct
2 Correct 2284 ms 379900 KB Output is correct
3 Correct 1774 ms 316312 KB Output is correct
4 Correct 1924 ms 320136 KB Output is correct
5 Correct 1731 ms 315552 KB Output is correct
6 Correct 2648 ms 334324 KB Output is correct
7 Correct 2402 ms 330068 KB Output is correct
8 Correct 2488 ms 332620 KB Output is correct
9 Correct 2212 ms 327700 KB Output is correct
10 Correct 2183 ms 326748 KB Output is correct
11 Correct 2163 ms 326600 KB Output is correct
12 Correct 2268 ms 328700 KB Output is correct