Submission #691870

#	Time	Username	Problem	Language	Result	Execution time	Memory
691870		piOOE	Prize (CEOI22_prize)	C++17	100 / 100	2398 ms	243184 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24