社区讨论

求助

kkczno1
P3542[POI 2012] PEN-Salaries参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi5his9c
此快照首次捕获于
2025/11/19 12:10
4 个月前
此快照最后确认于
2025/11/19 12:10
4 个月前
查看原帖
应该是父亲一定比儿子大。。
所以每个点的max就是父亲-1，还要用已知的更新一下max，也就是说让max向下取至第一个未被取过的。
之后如果=max的只有它一个就是确定的，否则就是不确定的。
但是wa了，但我又找不到反例。。
求解为什么错。
CPP
#include<bits/stdc++.h>

#define N 1000100
int f[N],w[N],pre[N];
int cnt[N];
int t[N],next[N];
int q[N],head,tail;
int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    int n,rt,i;scanf("%d",&n);
    for (i=1;i<=n;++i) 
    {
        scanf("%d%d",f+i,w+i);
        if (f[i]==i) {rt=i;w[i]=n;} 
        else {next[i]=t[f[i]];t[f[i]]=i;}
        if (w[i]) pre[w[i]]=1;
    }
    for (i=1;i<=n;++i) 
    if (!pre[i]) pre[i]=i;
    else pre[i]=pre[i-1];
    
    q[tail=1]=rt;
    for (head=1;head<=tail;++head)
    {
        int x=q[head];
        for (i=t[x];i;i=next[i]) q[++tail]=i;
        if (w[x]) continue;
        w[x]=pre[w[f[x]]-1];
        ++cnt[w[x]]; 
    }
    for (i=1;i<=n;++i) 
    if (cnt[w[i]]>1) puts("0");
    else printf("%d\n",w[i]);
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...