oj.uz

Submission #691869

# Submission time Handle Problem Language Result Execution time Memory
691869 2023-01-31T19:22:05 Z piOOE Prize (CEOI22_prize) C++17
100 / 100
 2522 ms 243396 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;
    
    int root[2]{};
    
    for (int i = 0; i < 2; ++i) {
        vector<vector<int>> adj(n);
        
        for (int j = 0; j < n; ++j) {
            int p;
            cin >> p;
            
            if (p == -1) {
                root[i] = j;
            } else {
                adj[p - 1].push_back(j);
            }
        }
        
        tree[i].init(adj, root[i]);
    }

    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 h1 = ord[0], h2 = ord[0];

    vector<int> aa, bb;
    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);
            addEdge(i, c, x, dx);
            addEdge(i, c, y, dy);
        }
    }

    auto first = normalize(n, h1, g[0]);
    auto second = normalize(n, h2, 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:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 1; i < ord.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 121852 KB Output is correct
2 Correct 1184 ms 123696 KB Output is correct
3 Correct 818 ms 73192 KB Output is correct
4 Correct 879 ms 73120 KB Output is correct
5 Correct 884 ms 75552 KB Output is correct
6 Correct 1074 ms 84160 KB Output is correct
7 Correct 1104 ms 84168 KB Output is correct
8 Correct 1105 ms 84196 KB Output is correct
9 Correct 824 ms 73240 KB Output is correct
10 Correct 866 ms 75068 KB Output is correct
11 Correct 800 ms 71204 KB Output is correct
12 Correct 928 ms 75080 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 123768 KB Output is correct
2 Correct 1134 ms 121816 KB Output is correct
3 Correct 885 ms 73228 KB Output is correct
4 Correct 1018 ms 76852 KB Output is correct
5 Correct 868 ms 75128 KB Output is correct
6 Correct 1037 ms 84256 KB Output is correct
7 Correct 1207 ms 86088 KB Output is correct
8 Correct 1239 ms 86104 KB Output is correct
9 Correct 1058 ms 86188 KB Output is correct
10 Correct 1052 ms 86520 KB Output is correct
11 Correct 987 ms 84272 KB Output is correct
12 Correct 1129 ms 86088 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 899 ms 121768 KB Output is correct
2 Correct 876 ms 121828 KB Output is correct
3 Correct 605 ms 71232 KB Output is correct
4 Correct 626 ms 71324 KB Output is correct
5 Correct 605 ms 71116 KB Output is correct
6 Correct 749 ms 84116 KB Output is correct
7 Correct 712 ms 84224 KB Output is correct
8 Correct 698 ms 84212 KB Output is correct
9 Correct 657 ms 84060 KB Output is correct
10 Correct 666 ms 84096 KB Output is correct
11 Correct 691 ms 84284 KB Output is correct
12 Correct 661 ms 84112 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2098 ms 243148 KB Output is correct
2 Correct 1933 ms 243396 KB Output is correct
3 Correct 1424 ms 142048 KB Output is correct
4 Correct 1412 ms 142124 KB Output is correct
5 Correct 1467 ms 142160 KB Output is correct
6 Correct 1901 ms 167952 KB Output is correct
7 Correct 1721 ms 167904 KB Output is correct
8 Correct 1726 ms 167932 KB Output is correct
9 Correct 1706 ms 167952 KB Output is correct
10 Correct 1614 ms 167872 KB Output is correct
11 Correct 1577 ms 167960 KB Output is correct
12 Correct 1620 ms 168052 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2522 ms 243148 KB Output is correct
2 Correct 2324 ms 243168 KB Output is correct
3 Correct 1644 ms 145920 KB Output is correct
4 Correct 1700 ms 142124 KB Output is correct
5 Correct 1625 ms 142080 KB Output is correct
6 Correct 2140 ms 155692 KB Output is correct
7 Correct 2113 ms 167956 KB Output is correct
8 Correct 2132 ms 168020 KB Output is correct
9 Correct 1859 ms 167972 KB Output is correct
10 Correct 1884 ms 168004 KB Output is correct
11 Correct 1840 ms 167844 KB Output is correct
12 Correct 1888 ms 167940 KB Output is correct