VP 2025 ICPC 西安

The 2025 ICPC Asia Xi’an Regional Contest
The 4th Universal Cup. Extra Stage 1: Xi’an (Unrated)
Date 2025/11/13
Solved 5 / 13

A	B	C	D	E	F	G	H	I	J	K	L	M
					O	O		O	O		O

I - Imagined Holly

根据经典的 A[u][v] = A[1][u] ^ A[1][v] ^ lca(u, v)，可以 $O(n^2)$ 枚举点对并得到 lca，拓扑排序一下即可得到原图

void solve() {
    int n = read();

    vector a(n + 1, vector(n + 1, 0ll));
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            a[i][j] = a[j][i] = read();
        }
    }

    vector<vector<int>> adj(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int lca = a[i][j] ^ a[1][i] ^ a[1][j];
            if (lca != i) adj[lca].eb(i);
            if (lca != j) adj[lca].eb(j);
        }
    }

    vector<int> ind(n + 1);
    for (int i = 1; i <= n; i++) {
        for (int j : adj[i]) ind[j]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!ind[i]) q.ep(i);
    }

    vector<pii> ans;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (!--ind[v]) {
            ans.eb(u, v), q.ep(v);
        }
    }

    for (auto [x, y] : ans) {
        cout << x << " " << y << '\n';
    }
}

F - Follow the Penguins

用堆维护相遇事件

struct node {
    int x, k, tim;
    bool friend operator < (node i, node j) {
        return i.tim > j.tim;
    }
};

void solve() {
    int n = read();

    vector<int> t(n + 1);
    for (int i = 1; i <= n; i++) t[i] = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read() * 2;

    vector<vector<int>> buk(n + 1);
    for (int i = 1; i <= n; i++) {
        buk[t[i]].eb(i);
    }

    auto sign = [&](int x) -> int {
        return x > 0 ? 1 : -1;
    };

    priority_queue<node> pq;
    for (int i = 1; i <= n; i++) {
        int tim = 0;
        int x = i, y = t[x], z = t[y];
        if (sign(a[y] - a[x]) == sign(a[z] - a[y])) {
            continue;
        } else {
            tim = abs(a[y] - a[x]) / 2;
        }

        // cout << "push: " << x << ' ' << y << ' ' << tim << "\n";
        pq.ep(x, 0, tim);

    }

    vector<int> stop(n + 1);
    vector<int> ans(n + 1);
    vector<int> cnt(n + 1);

    while (!pq.empty()) {
        auto [x, k, tim] = pq.top(); pq.pop();
        if (stop[x]) continue;
        if (cnt[x] != k) continue;

        // cout << "pop: " << x << ' ' << y << ' ' << tim << '\n';
        ans[x] = tim;
        stop[x] = 1;

        int y = t[x];
        a[x] += sign(a[y] - a[x]) * tim;

        for (auto t : buk[x]) {
            if (stop[t]) continue;
            cnt[t]++;
            pq.ep(t, 1, abs(a[x] - a[t]));
            // cout << "push: " << t << ' ' << x << ' ' << ntim << "\n";
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

J - January’s Color

void solve() {
    int n = read(), q = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();

    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        adj[u].eb(v), adj[v].eb(u);
    }

    vector<int> dfin(n + 1), dfou(n + 1);
    int timer = 0;

    vector<int> f(n + 1);
    vector<int> g(n + 1);
    vector<int> sum(n + 1);

    [&](this auto&& dfs, int u, int fa) -> void {
        dfin[u] = ++timer;
        f[u] = a[u];
        if (fa) {
            adj[u].erase(ranges::find(adj[u], fa));
        }

        vector<int> t;
        for (int v : adj[u]) {
            dfs(v, u);
            t.eb(f[v]);
        }
        dfou[u] = timer;

        if (adj[u].empty()) return;
        int m = adj[u].size();

        auto pre = t;
        for (int i = 1; i < m; i++) cmin(pre[i], pre[i - 1]);
        auto suf = t;
        for (int i = m - 2; i >= 0; i--) cmin(suf[i], suf[i + 1]);

        for (int i = 0; i < m; i++) {
            int v = adj[u][i];
            g[v] = inf;
            if (i > 0) cmin(g[v], pre[i - 1]);
            if (i < m - 1) cmin(g[v], suf[i + 1]);
        }

        ranges::sort(t);
        cmin(f[u], t[0] + t[1]);
        
    } (1, 0);

    [&](this auto&& dfs, int u) -> void {
        for (int v : adj[u]) {
            sum[v] = g[v] + sum[u];
            dfs(v);
        }
    } (1);

    for (int i = 1; i <= q; i++) {
        int x = read(), y = read();
        int res = -1;
        if (dfin[y] <= dfin[x] and dfou[x] <= dfou[y]) {
            res = sum[x] - sum[y];
        }
        cout << res << '\n';
    }
}

L - Let’s Make a Convex!

void solve() {
    int n = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();
    sort(a.begin() + 1, a.end());
    auto s = a;

    for (int i = 1; i <= n; i++) {
        s[i] += s[i - 1];
    }

    vector<int> pos(n + 2);
    pos[n + 1] = n;
    vector<int> ans(n + 2);
    for (int k = n; k >= 3; k--) {
        pos[k] = pos[k + 1];
        for (int i = pos[k + 1]; i >= k; i--) {
            if (s[i] - s[i - k] > 2 * a[i]) {
                pos[k] = i;
                ans[k] = s[i] - s[i - k];
                break;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

G - Grand Voting

void solve() {
    int n = read();

    vector<int> a(n);
    for (int &x : a) x = read();

    ranges::sort(a);
    
    int s1 = 0;
    for (int x : a) {
        if (x <= s1) s1++;
        else s1--;
    }

    int s2 = 0;
    auto b = a;
    ranges::reverse(b);

    // debug(a);
    // debug(b);

    for (int x : b) {
        if (x <= s2) s2++;
        else s2--;
    }

    cout << s1 << ' ' << s2 << '\n';
}