oj.uz

Submission #726047

# Submission time Handle Problem Language Result Execution time Memory
726047 2023-04-18T11:17:06 Z tengiz05 Prize (CEOI22_prize) C++17
100 / 100
 2548 ms 380444 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();
    int newRoot = f[0];
    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);
        if (t2.in[l] < t2.in[newRoot]) {
            newRoot = l;
        }
        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(newRoot);
    
    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 1079 ms 239552 KB Output is correct
2 Correct 1139 ms 242076 KB Output is correct
3 Correct 887 ms 209664 KB Output is correct
4 Correct 892 ms 209176 KB Output is correct
5 Correct 931 ms 211824 KB Output is correct
6 Correct 1247 ms 217556 KB Output is correct
7 Correct 1238 ms 217776 KB Output is correct
8 Correct 1276 ms 216856 KB Output is correct
9 Correct 916 ms 209576 KB Output is correct
10 Correct 928 ms 211168 KB Output is correct
11 Correct 896 ms 208176 KB Output is correct
12 Correct 923 ms 210680 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 242336 KB Output is correct
2 Correct 1084 ms 238360 KB Output is correct
3 Correct 967 ms 209628 KB Output is correct
4 Correct 1154 ms 212008 KB Output is correct
5 Correct 1004 ms 210352 KB Output is correct
6 Correct 1295 ms 215568 KB Output is correct
7 Correct 1383 ms 218596 KB Output is correct
8 Correct 1451 ms 218992 KB Output is correct
9 Correct 1321 ms 217000 KB Output is correct
10 Correct 1302 ms 217684 KB Output is correct
11 Correct 1251 ms 214224 KB Output is correct
12 Correct 1260 ms 217688 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 945 ms 229900 KB Output is correct
2 Correct 1033 ms 230052 KB Output is correct
3 Correct 696 ms 199532 KB Output is correct
4 Correct 697 ms 199644 KB Output is correct
5 Correct 721 ms 199444 KB Output is correct
6 Correct 892 ms 206628 KB Output is correct
7 Correct 851 ms 206648 KB Output is correct
8 Correct 824 ms 206648 KB Output is correct
9 Correct 798 ms 204616 KB Output is correct
10 Correct 784 ms 204560 KB Output is correct
11 Correct 756 ms 204492 KB Output is correct
12 Correct 797 ms 204532 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2099 ms 368288 KB Output is correct
2 Correct 2009 ms 368408 KB Output is correct
3 Correct 1484 ms 307620 KB Output is correct
4 Correct 1528 ms 307532 KB Output is correct
5 Correct 1500 ms 307588 KB Output is correct
6 Correct 2021 ms 321808 KB Output is correct
7 Correct 1963 ms 321932 KB Output is correct
8 Correct 1983 ms 321836 KB Output is correct
9 Correct 1794 ms 317612 KB Output is correct
10 Correct 1777 ms 317636 KB Output is correct
11 Correct 1951 ms 317464 KB Output is correct
12 Correct 1934 ms 317636 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2291 ms 380444 KB Output is correct
2 Correct 2201 ms 379956 KB Output is correct
3 Correct 1783 ms 316316 KB Output is correct
4 Correct 1810 ms 320208 KB Output is correct
5 Correct 1712 ms 315508 KB Output is correct
6 Correct 2548 ms 334404 KB Output is correct
7 Correct 2392 ms 330100 KB Output is correct
8 Correct 2498 ms 332596 KB Output is correct
9 Correct 2250 ms 327656 KB Output is correct
10 Correct 2390 ms 326528 KB Output is correct
11 Correct 2230 ms 326736 KB Output is correct
12 Correct 2217 ms 328652 KB Output is correct