题解 P9464 [EGOI2023] Padel Prize Pursuit

GI录像机 · 2023-10-30 11:44:13 · 题解

思路：

容易发现当一些奖牌同时被一个人获取以后，这些奖牌之后的命运将会完全一致。

这就很像是树上的节点往上走，lca 后的祖先都是一样的。

我们可以利用树的结构来完成操作。

每当一个选手 x 打败选手 y 时，会出现一个全新的奖牌 i。我们可以将选手 x 和 y 原有的奖牌连接到 i 上。这样等到 x 被打败时，i 子树内的奖牌被 x 持有的时间就会增加。这样，每个选手在任意时刻持有的奖牌都是一棵完整的树，操作时我们只需要对树根连边即可。

结束时，直接遍历每一棵树，计算奖牌在谁手中持有的时间最长。

代码：

#include<bits/stdc++.h>
using namespace std;
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return f * x;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
struct Edge {
    int to, nxt;
} e[N];
int n = read(), m = read(), las[N], head[N], tot, id[N], num[N], sum[N], ans[N];
void add(int u, int v) {
    e[++tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
void dfs(int pos, int maxn, int maxnid) {
    sum[id[pos]] += num[pos];
    if (sum[id[pos]] > maxn) {
        maxn = sum[id[pos]];
        maxnid = id[pos];
    } else if (sum[id[pos]] == maxn)maxnid = min(maxnid, id[pos]);
    ans[maxnid]++;
    for (int i = head[pos]; i; i = e[i].nxt)dfs(e[i].to, maxn, maxnid);
    sum[id[pos]] -= num[pos];
}
signed main() {
    memset(las, -1, sizeof(las));
    for (int i = 0; i < m; i++) {
        int x = read(), y = read();
        if (las[x] != -1) {
            id[las[x]] = x;
            num[las[x]] = i - las[x];
            add(i, las[x]);
        }
        if (las[y] != -1) {
            id[las[y]] = y;
            num[las[y]] = i - las[y];
            add(i, las[y]);
        }
        las[y] = -1;
        las[x] = i;
    }
    for (int i = 0; i < n; i++)
        if (las[i] != -1) {
            id[las[i]] = i;
            num[las[i]] = m - las[i];
            dfs(las[i], 0, 0);
        }
    for (int i = 0; i < n; i++) {
        write(ans[i]);
        putchar(' ');
    }
    return 0;
}