Submission #726576

#	Time	Username	Problem	Language	Result	Execution time	Memory
726576		MadokaMagicaFan	Prize (CEOI22_prize)	C++14	100 / 100	2977 ms	411480 KiB

Main

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

#define sz(v)   ((int)(v).size())
#define N 1000000
#define logN 22


struct tree {
    int n;
    int r;
    int d[N], et[N];
    vector<array<int, logN>> j;
    ll h[N];
    vector<vector<int>> adj;
    vector<array<ll, 2>> dadj[N];
    bitset<N> vis;
    int ec;

    void
    _cheight(int i, int _d)
    {
        d[i] = _d;
        et[i] = ec++;
        for (auto x : adj[i]) {
            if (j[i][0] != x)
                _cheight(x, _d+1);
        }
    }

    void
    init(int _n, vector<int>& _p)
    {
        n = _n;
        ec = 0;
        vis = 0;
        adj.resize(n);
        j.resize(n);
        assert(sz(_p) == n);
        for (int i = 0; i < n; ++i) {
            if (_p[i] == -2) {
                r = i;
                j[i][0] = i;
            } else {
                j[i][0] = _p[i];
                adj[i].push_back(_p[i]);
                adj[_p[i]].push_back(i);
            }
        }

        for (int k = 1; k < logN; ++k) {
            for (int i = 0; i < n; ++i) {
                j[i][k] = j[j[i][k-1]][k-1];
            }
        }

        _cheight(r,0);
    }

    int
    lca(int a, int b)
    {
        if (d[a] < d[b])
            swap(a,b);

        for (int k = 0; k < logN; ++k) {
            if (((d[a] - d[b]) >> k) & 1)
                a = j[a][k];
        }

        if (a == b) return a;
        for (int k = logN-1; k >= 0; --k) {
            if (j[a][k] != j[b][k]) {
                a = j[a][k];
                b = j[b][k];
            }
        }
        return j[a][0];
    }

    void
    doheight(int x, ll val)
    {
        if (vis[x]) return;
        vis[x] = 1;
        h[x] = val;

        for (auto u : dadj[x])
            doheight(u[0], val + u[1]);
    }
};
tree t1, t2;
int nodes[N+2], ns;

void
dfs1(int x, int k)
{
    if (ns == k) return;
    nodes[ns++] = x;
    for (auto u : t1.adj[x]) {
        if (t1.j[x][0] != u)
            dfs1(u, k);
    }
}

int
cmp(const void *a, const void *b)
{
    return t2.et[*((int *)a)] - t2.et[*((int *)b)];
}

int
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    vector<array<ll, 2>> ans(t);

    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i]; --p[i];
    }
    t1.init(n, p);

    for (int i = 0; i < n; ++i) {
        cin >> p[i]; --p[i];
    }
    t2.init(n, p);

    dfs1(t1.r, k);
    qsort(nodes, k, sizeof *nodes, cmp);

    for (int i = 0; i < k; ++i) {
        cout << nodes[i] + 1 << ' ';
    }
    cout << '\n';

    for (int i = 0; i < k-1; ++i)
        cout << "? " << nodes[i] + 1 << ' ' << nodes[i+1] + 1 << '\n';
    cout << "!\n"; cout.flush();

    for (int i = 0; i < k-1; ++i) {
        int x, y, l;
        cin >> x >> y;
        l = t1.lca(nodes[i], nodes[i+1]);
        t1.dadj[nodes[i]].push_back({l, -x});
        t1.dadj[l].push_back({nodes[i], x});
        t1.dadj[nodes[i+1]].push_back({l, -y});
        t1.dadj[l].push_back({nodes[i+1], y});

        cin >> x >> y;
        l = t2.lca(nodes[i], nodes[i+1]);
        t2.dadj[nodes[i]].push_back({l, -x});
        t2.dadj[l].push_back({nodes[i], x});
        t2.dadj[nodes[i+1]].push_back({l, -y});
        t2.dadj[l].push_back({nodes[i+1], y});
    }

    t1.doheight(nodes[0], 0);
    t2.doheight(nodes[0], 0);


    for (int i = 0; i < t; ++i) {
        int a, b, l;
        cin >> a >> b; --a; --b;

        l = t1.lca(a, b);
        ans[i][0] = t1.h[a] + t1.h[b] - 2ll * t1.h[l];
        l = t2.lca(a, b);
        ans[i][1] = t2.h[a] + t2.h[b] - 2ll * t2.h[l];
    }

    for (int i = 0; i < t; ++i)
        cout << ans[i][0] << ' ' << ans[i][1] << endl;
    cout.flush();
}

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