oj.uz

Submission #726048

# Submission time Handle Problem Language Result Execution time Memory
726048 2023-04-18T11:23:15 Z tengiz05 Prize (CEOI22_prize) C++17
100 / 100
 2806 ms 380524 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);
        }
    }
    std::sort(f.begin(), f.end(), [&](int i, int j) {
        return t1.in[i] < t1.in[j];
    });
    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 1127 ms 239576 KB Output is correct
2 Correct 1184 ms 242080 KB Output is correct
3 Correct 956 ms 209660 KB Output is correct
4 Correct 960 ms 209216 KB Output is correct
5 Correct 1083 ms 211712 KB Output is correct
6 Correct 1325 ms 217548 KB Output is correct
7 Correct 1283 ms 217760 KB Output is correct
8 Correct 1274 ms 216840 KB Output is correct
9 Correct 962 ms 209552 KB Output is correct
10 Correct 981 ms 211296 KB Output is correct
11 Correct 909 ms 208304 KB Output is correct
12 Correct 1006 ms 210664 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1234 ms 242292 KB Output is correct
2 Correct 1150 ms 238416 KB Output is correct
3 Correct 999 ms 209660 KB Output is correct
4 Correct 1091 ms 211980 KB Output is correct
5 Correct 1087 ms 210320 KB Output is correct
6 Correct 1366 ms 215712 KB Output is correct
7 Correct 1492 ms 218704 KB Output is correct
8 Correct 1570 ms 218896 KB Output is correct
9 Correct 1309 ms 217000 KB Output is correct
10 Correct 1451 ms 217700 KB Output is correct
11 Correct 1273 ms 214080 KB Output is correct
12 Correct 1424 ms 217552 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 229992 KB Output is correct
2 Correct 1016 ms 229916 KB Output is correct
3 Correct 701 ms 199536 KB Output is correct
4 Correct 673 ms 199560 KB Output is correct
5 Correct 778 ms 199532 KB Output is correct
6 Correct 884 ms 206576 KB Output is correct
7 Correct 856 ms 206628 KB Output is correct
8 Correct 861 ms 206676 KB Output is correct
9 Correct 805 ms 204700 KB Output is correct
10 Correct 806 ms 204576 KB Output is correct
11 Correct 816 ms 204588 KB Output is correct
12 Correct 812 ms 204496 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2125 ms 368360 KB Output is correct
2 Correct 2092 ms 368372 KB Output is correct
3 Correct 1463 ms 307648 KB Output is correct
4 Correct 1588 ms 307660 KB Output is correct
5 Correct 1496 ms 307404 KB Output is correct
6 Correct 2217 ms 321828 KB Output is correct
7 Correct 1952 ms 321760 KB Output is correct
8 Correct 2021 ms 321736 KB Output is correct
9 Correct 1810 ms 317772 KB Output is correct
10 Correct 1798 ms 317748 KB Output is correct
11 Correct 1809 ms 317576 KB Output is correct
12 Correct 1749 ms 317536 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2293 ms 380524 KB Output is correct
2 Correct 2242 ms 379932 KB Output is correct
3 Correct 1731 ms 316420 KB Output is correct
4 Correct 1854 ms 320104 KB Output is correct
5 Correct 1697 ms 315772 KB Output is correct
6 Correct 2806 ms 334356 KB Output is correct
7 Correct 2403 ms 330288 KB Output is correct
8 Correct 2485 ms 332576 KB Output is correct
9 Correct 2177 ms 327640 KB Output is correct
10 Correct 2145 ms 326636 KB Output is correct
11 Correct 2132 ms 326700 KB Output is correct
12 Correct 2231 ms 328672 KB Output is correct