oj.uz

Submission #691870

# Submission time Handle Problem Language Result Execution time Memory
691870 2023-01-31T19:25:04 Z piOOE Prize (CEOI22_prize) C++17
100 / 100
 2398 ms 243184 KB 
#include <bits/stdc++.h>

using namespace std;

struct Tree {
    vector<int> tin, tout, par, depth, jump;
    int logn;

    void init(vector<vector<int>> adj, int root) {
        int n = adj.size();
        int T = 0;

        tin.assign(n, -1), tout.resize(n), par.resize(n), depth.resize(n), jump.resize(n);

        par[root] = jump[root] = root;

        function<void(int)> dfs = [&](int v) {
            tin[v] = T++;
            for (int to : adj[v]) {
                depth[to] = depth[v] + 1;
                par[to] = v;

                int p = jump[v];
                int pp = jump[p];
                if (depth[p] - depth[v] == depth[pp] - depth[p]) {
                    jump[to] = pp;
                } else {
                    jump[to] = v;
                }

                dfs(to);
            }
            tout[v] = T;
        };

        dfs(root);

        logn = __lg(n) + 1;
    }

    bool isp(int a, int b) {
        return tin[a] <= tin[b] && tout[a] >= tout[b];
    }

    int lca(int a, int b) {
        if (isp(a, b)) {
            return a;
        }

        while (!isp(par.at(a), b)) {
            if (isp(jump[a], b)) {
                a = par[a];
            } else {
                a = jump[a];
            }
        }

        return par[a];
    }
} tree[2];

vector<int> normalize(int n, int root, vector<vector<pair<int, int>>> g) {
    vector<int> dist(n, -1);
    dist[root] = 0;
    vector<bool> used(n);

    function<void(int)> dfs = [&](int v) {
        used[v] = true;
        for (auto [to, w]: g.at(v)) {
            if (!used[to]) {
                dist[to] = dist[v] + w;
                dfs(to);
            }
        }
    };

    dfs(root);

    return dist;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q, t;
    cin >> n >> k >> q >> t;
    
    for (int i = 0; i < 2; ++i) {
        vector<vector<int>> adj(n);

        int root = 0;
        
        for (int j = 0; j < n; ++j) {
            int p;
            cin >> p;

            if (p == -1) {
                root = j;
            } else {
                adj[p - 1].push_back(j);
            }
        }

        tree[i].init(adj, root);
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);

    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return tree[0].tin[i] < tree[0].tin[j];
    });

    ord.resize(k);

    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return tree[1].tin[i] < tree[1].tin[j];
    });

    for (int x : ord) {
        cout << x + 1 << " \n"[x == ord.back()];
    }
    
    vector<pair<int, int>> questions;
    
    for (int i = 1; i < ord.size(); ++i) {
        questions.emplace_back(ord[i - 1], ord[i]);
    }

    for (auto [x, y]: questions) {
        cout << "? " << x + 1 << " " << y + 1 << '\n';
    }
    cout << "!" << endl;

    vector g(2, vector<vector<pair<int, int>>>(n));

    int h[2]{ord[0], ord[0]};

    auto addEdge = [&](int tt, int x, int y, int w) {
        g[tt][x].emplace_back(y, w);
        g[tt][y].emplace_back(x, -w);
    };

    for (auto [x, y] : questions) {
        for (int i = 0; i < 2; ++i) {
            int dx, dy;
            cin >> dx >> dy;

            int c = tree[i].lca(x, y);
            
            if (tree[i].isp(c, h[i])) {
                h[i] = c;
            }
            
            addEdge(i, c, x, dx);
            addEdge(i, c, y, dy);
        }
    }

    auto first = normalize(n, h[0], g[0]);
    auto second = normalize(n, h[1], g[1]);

    vector<pair<int, int>> queries(t);
    for (auto &[a, b] : queries) {
        cin >> a >> b;
        a -= 1, b -= 1;
    }

    for (auto [a, b]: queries) {
        int dist1 = first[a] - 2 * first[tree[0].lca(a, b)] + first[b];
        int dist2 = second[a] - 2 * second[tree[1].lca(a, b)] + second[b];

        cout << dist1 << " " << dist2 << '\n';
    }

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 1; i < ord.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 121764 KB Output is correct
2 Correct 1218 ms 123784 KB Output is correct
3 Correct 799 ms 73236 KB Output is correct
4 Correct 843 ms 73364 KB Output is correct
5 Correct 920 ms 75352 KB Output is correct
6 Correct 1012 ms 84124 KB Output is correct
7 Correct 988 ms 84192 KB Output is correct
8 Correct 1020 ms 84208 KB Output is correct
9 Correct 797 ms 73160 KB Output is correct
10 Correct 824 ms 75152 KB Output is correct
11 Correct 820 ms 71224 KB Output is correct
12 Correct 871 ms 75352 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 123832 KB Output is correct
2 Correct 1124 ms 121928 KB Output is correct
3 Correct 880 ms 73156 KB Output is correct
4 Correct 898 ms 76996 KB Output is correct
5 Correct 869 ms 75356 KB Output is correct
6 Correct 1083 ms 84296 KB Output is correct
7 Correct 1142 ms 86116 KB Output is correct
8 Correct 1160 ms 86188 KB Output is correct
9 Correct 1067 ms 86108 KB Output is correct
10 Correct 1093 ms 86652 KB Output is correct
11 Correct 1006 ms 84224 KB Output is correct
12 Correct 1028 ms 86140 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 121768 KB Output is correct
2 Correct 884 ms 121900 KB Output is correct
3 Correct 643 ms 71264 KB Output is correct
4 Correct 633 ms 71148 KB Output is correct
5 Correct 621 ms 71160 KB Output is correct
6 Correct 702 ms 84352 KB Output is correct
7 Correct 733 ms 84276 KB Output is correct
8 Correct 704 ms 84116 KB Output is correct
9 Correct 650 ms 84136 KB Output is correct
10 Correct 658 ms 84184 KB Output is correct
11 Correct 650 ms 84180 KB Output is correct
12 Correct 661 ms 84280 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2020 ms 243040 KB Output is correct
2 Correct 1981 ms 243184 KB Output is correct
3 Correct 1437 ms 142228 KB Output is correct
4 Correct 1424 ms 142000 KB Output is correct
5 Correct 1427 ms 141992 KB Output is correct
6 Correct 1767 ms 167856 KB Output is correct
7 Correct 1757 ms 167948 KB Output is correct
8 Correct 1727 ms 168160 KB Output is correct
9 Correct 1569 ms 167920 KB Output is correct
10 Correct 1554 ms 167932 KB Output is correct
11 Correct 1606 ms 167916 KB Output is correct
12 Correct 1600 ms 167980 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2378 ms 243120 KB Output is correct
2 Correct 2398 ms 243080 KB Output is correct
3 Correct 1642 ms 145956 KB Output is correct
4 Correct 1710 ms 142128 KB Output is correct
5 Correct 1592 ms 142256 KB Output is correct
6 Correct 2159 ms 155700 KB Output is correct
7 Correct 2079 ms 167960 KB Output is correct
8 Correct 2100 ms 167948 KB Output is correct
9 Correct 1877 ms 167908 KB Output is correct
10 Correct 1946 ms 167940 KB Output is correct
11 Correct 1840 ms 167844 KB Output is correct
12 Correct 1906 ms 167992 KB Output is correct