Submission #1107225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107225		Sharky	Prize (CEOI22_prize)	C++17	0 / 100	1480 ms	375984 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 20;
const int LG = 20;

vector<int> node;

struct Tree {
    int n, rt, timer = 0, lift[N][LG], p[N], dep[N], tin[N], ps[N];
    vector<int> adj[N];
    vector<pair<int, int>> g[N];
    int jump(int sta, int dist) {
        for (int i = LG - 1; i >= 0; i--) 
            if ((1 << i) & dist) sta = lift[sta][i];
        return sta;
    }
    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        x = jump(x, dep[x] - dep[y]);
        if (x == y) return x;
        for (int i = LG - 1; i >= 0; i--) {
            int xt = lift[x][i], yt = lift[y][i];
            if (xt != yt) x = xt, y = yt;
        }
        return lift[x][0];
    }
    void dfs(int u, int pa, int k, bool pushing = 0) {
        tin[u] = ++timer;
        for (int i = 1; i < LG; i++) lift[u][i] = lift[lift[u][i-1]][i-1];
        if (pushing && (int) node.size() < k) node.push_back(u);
        for (int v : adj[u]) {
            if (v == pa) continue;
            lift[v][0] = u;
            dep[v] = dep[u] + 1;
            dfs(v, u, k, pushing);
        }
    }
    void init(int _n, int k, bool pushing = 0) {
        n = _n;
        for (int i = 1; i <= n; i++) {
            cin >> p[i];
            if (p[i] != -1) adj[p[i]].push_back(i);
            else rt = i;
        }
        lift[rt][0] = rt;
        dfs(rt, -1, k, pushing);
    }
    void add(int u, int v, int w) {
        g[u].push_back({v, w});
        g[v].push_back({u, -w});
    }
    void solve(int sc) {
        queue<int> bfs;
        ps[sc] = 1;
        bfs.push(sc);
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            for (auto& [v, w] : g[u]) if (!ps[v]) {
                ps[v] = ps[u] + w;
                bfs.push(v);
            }
        }
    }
    int get_ans(int u, int v) {
        return ps[u] + ps[v] - ps[lca(u, v)] * 2;
    }
} S, T; // cont, non-cont

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k, q, t;
    cin >> n >> k >> q >> t;
    S.init(n, k, 1); T.init(n, k, 0);
    sort(node.begin(), node.end(), [&] (int x, int y) {
        return T.tin[x] < T.tin[y];
    });
    // assert((int) node.size() == k);
    for (int i = 0; i < k; i++) {
        cout << node[i];
        if (i == k - 1) cout << '\n';
        else cout << ' ';
    }
    fflush(stdout);
    for (int i = 1; i < k; i++) cout << "? " << node[i-1] << " " << node[i] << '\n';
    cout << "!\n"; fflush(stdout);
    int LCA = node[0];
    for (int i = 1; i < k; i++) {
        int lcas = S.lca(node[i-1], node[i]);
        int lcat = T.lca(node[i-1], node[i]);
        LCA = T.lca(LCA, node[i]);
        int su, sv, tu, tv;
        cin >> su >> sv >> tu >> tv;
        S.add(lcas, node[i-1], su); S.add(lcas, node[i], sv);
        T.add(lcat, node[i-1], tu); T.add(lcat, node[i], tv);
    }
    S.solve(S.rt); T.solve(LCA);
    vector<pair<int, int>> que;
    while (t--) {
        int u, v;
        cin >> u >> v;
        que.push_back({u, v});
    }
    for (auto& [u, v] : que) cout << S.ps[u] + S.ps[v] - S.ps[S.lca(u, v)] * 2 << " " << T.ps[u] + T.ps[v] - T.ps[T.lca(u, v)] * 2 << '\n';
    cout << '\n';
    fflush(stdout);
}

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

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