Submission #1222681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222681		omsincoconut	Prize (CEOI22_prize)	C++17	100 / 100	1262 ms	331868 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, K, Q, T;

struct MinSegtree{
    int n;
    vector<pair<int, int>> tree;

    void init(vector<pair<int, int>> val) {
        n = val.size();
        tree = vector<pair<int, int>>(2*n, {INT_MAX, INT_MAX});
        for (int i = 0; i < n; i++) tree[n+i] = val[i];
        for (int i = n-1; i >= 1; i--) tree[i] = min(tree[i<<1], tree[(i<<1)|1]);
    }

    pair<int, int> query(int l, int r) {
        r++;
        pair<int, int> ret = {INT_MAX, INT_MAX};
        for (l += n, r += n; l < r; l>>=1, r>>=1) {
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
};

struct Tree{
    int n, root;
    vector<int> p;
    vector<vector<int>> child;

    vector<int> tin, depth, ord;
    MinSegtree segtree;

    int cte = -1;
    void gen_ett(int u) {
        tin[u] = ++cte;
        ord.push_back(u);

        for (int v : child[u]) {
            depth[v] = depth[u]+1;
            gen_ett(v);
            ++cte;
            ord.push_back(u);
        }
    }

    void readtree(int _n) {
        n = _n;
        p = tin = depth = vector<int>(n);
        child = vector<vector<int>>(n);

        for (int i = 0; i < n; i++) {
            cin >> p[i];
            if (p[i] == -1) root = i;
            else {
                p[i]--; // Change 1-based index to 0-based index
                child[p[i]].push_back(i);
            }
        }

        depth[root] = 0;
        gen_ett(root);

        vector<pair<int, int>> tmp(ord.size());
        for (int i = 0; i < ord.size(); i++)
            tmp[i] = make_pair(depth[ord[i]], ord[i]);

        segtree.init(tmp);
    }

    vector<int> sort_by_tin(vector<int> x) {
        sort(x.begin(), x.end(), [this](int a, int b) {
            return tin[a] < tin[b];
        });
        return x;
    }

    int lca(int u, int v) {
        return segtree.query(min(tin[u], tin[v]), max(tin[u], tin[v])).second;
    }
} tree1, tree2;

struct EqSolver{
    int n;
    vector<vector<pair<int, ll>>> edge;
    vector<ll> result;

    void init(int _n, vector<int> a, vector<int> b, vector<ll> c, int root) {
        n = _n;
        edge = vector<vector<pair<int, ll>>>(n);
        result = vector<ll>(n);

        for (int i = 0; i < a.size(); i++) {
            edge[a[i]].emplace_back(b[i], -c[i]);
            edge[b[i]].emplace_back(a[i], c[i]);
        }

        vector<bool> vis(n);
        queue<int> bfs;
        bfs.push(root);

        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            if (vis[u]) continue;
            vis[u] = true;

            for (auto [v, w] : edge[u]) {
                if (!vis[v]) {
                    result[v] = result[u]+w;
                    bfs.push(v);
                } 
            }
        }
    }
} solver1, solver2;

pair<vector<array<int, 4>>, vector<pair<int, int>>> query(vector<int> x, vector<int> u, vector<int> v) {
    for (int i : x)
        cout << i+1 << " "; // Change 0-based index to 1-based index
    cout << endl;

    int q = u.size();

    for (int i = 0; i < q; i++)
        cout << "? " << u[i]+1 << " " << v[i]+1 << "\n"; // Change 0-based index to 1-based index
    cout << "!" << endl;

    vector<array<int, 4>> ret1(q);
    for (int i = 0; i < q; i++) cin >> ret1[i][0] >> ret1[i][1] >> ret1[i][2] >> ret1[i][3];

    vector<pair<int, int>> ret2(T);
    for (int i = 0; i < T; i++) {
        cin >> ret2[i].first >> ret2[i].second;
        ret2[i].first--; ret2[i].second--; // Change 1-based index to 0-based index
    }

    return make_pair(ret1, ret2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K >> Q >> T;
    tree1.readtree(N);
    tree2.readtree(N);

    vector<int> x(N);
    iota(x.begin(), x.end(), 0);
    x = tree1.sort_by_tin(x);
    x.resize(K);
    x = tree2.sort_by_tin(x);

    vector<int> u(K-1), v(K-1);
    for (int i = 0; i < K-1; i++) u[i] = x[i], v[i] = x[i+1];
    
    auto [query_results, questions] = query(x, u, v);

    // Create solver1
    {
        vector<int> a(2*(K-1)), b(2*(K-1));
        vector<ll> c(2*(K-1));
        for (int i = 0; i < K-1; i++) {
            int lca_node = tree1.lca(u[i], v[i]);
            a[2*i] = u[i];
            b[2*i] = lca_node;
            c[2*i] = query_results[i][0];
            a[2*i+1] = v[i];
            b[2*i+1] = lca_node;
            c[2*i+1] = query_results[i][1];
        }

        solver1.init(N, a, b, c, u[0]);
    }

    // Create solver2
    {
        vector<int> a(2*(K-1)), b(2*(K-1));
        vector<ll> c(2*(K-1));
        for (int i = 0; i < K-1; i++) {
            int lca_node = tree2.lca(u[i], v[i]);
            a[2*i] = u[i];
            b[2*i] = lca_node;
            c[2*i] = query_results[i][2];
            a[2*i+1] = v[i];
            b[2*i+1] = lca_node;
            c[2*i+1] = query_results[i][3];
        }

        solver2.init(N, a, b, c, u[0]);
    }

    for (auto [a, b] : questions) {
        ll ans1 = solver1.result[a] + solver1.result[b] - 2*solver1.result[tree1.lca(a, b)];
        ll ans2 = solver2.result[a] + solver2.result[b] - 2*solver2.result[tree2.lca(a, b)];
        cout << ans1 << " " << ans2 << "\n";
    }
    cout << endl;

    return 0;
}

/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
*/

/*
10 0 0 1
0 3 13 5
4 2
4 1
1 2
*/

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24