QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412776#6561. Fail Fastgrass8cow#WA 1ms9940kbC++17921b2024-05-16 19:20:042024-05-16 19:20:05

Judging History

你现在查看的是最新测评结果

  • [2024-05-16 19:20:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9940kb
  • [2024-05-16 19:20:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
#define db double
int tim[201000];
db p[201000],q[201000];
int ff[201000],nxt[201000],R[201000],fa[201000];
struct qq{
    int u,ti;db p,q;
    bool operator < (const qq &a) const{
        return a.q+a.p*q<q+p*a.q;
    }
};
int F(int x){if(x==fa[x])return x;return fa[x]=F(fa[x]);}
priority_queue<qq>Q;
int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++)fa[i]=R[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%d",&p[i],&q[i],&ff[i]);
        Q.push((qq){i,0,p[i],q[i]});
    }
    while(!Q.empty()){
        qq uu=Q.top();Q.pop();int u=uu.u;
        if(tim[u]!=uu.ti||F(u)!=u)continue;
        int f=F(ff[u]);
        fa[u]=f,q[f]+=p[f]*q[u],p[f]*=p[u],tim[f]++;
        nxt[R[f]]=u;
        if(f)Q.push((qq){f,tim[f],p[f],q[f]});
        R[f]=R[u];
    }
    int u=nxt[0];while(u)printf("%d\n",u),u=nxt[u];
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9940kb

input:

4
100 0.5 0
200 0.1 1
10 0.5 2
10 0.9 0

output:

4
1
2
3

result:

ok correct

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 7904kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

1
3
4
2

result:

wrong answer your plan is not optimal