QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#235284 | #6561. Fail Fast | ugly2333 | WA | 1ms | 7800kb | C++20 | 923b | 2023-11-02 16:55:55 | 2023-11-02 16:55:55 |
Judging History
answer
//Δ_D
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
const int B = 1e6;
int n,b[N],f[N],l[N],r[N],nx[N],e[N];
DB t[N],p[N],a[N];
priority_queue<pair<DB,int> > Q;
int fnd(int x){
if(f[x]==x)
return x;
return f[x]=fnd(f[x]);
}
void mrg(int x,int y){//cout<<x<<' '<<y<<endl;
x=fnd(x);
y=fnd(y);
nx[r[x]]=l[y];
r[x]=r[y];
t[x]+=t[y];
p[x]*=p[y];
a[x]=t[x]/(1-p[x]);
if(x)
Q.push(make_pair(-a[x],x));
f[y]=x;
}
int main(){
int i,j,x;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%lf%lf%d",t+i,p+i,b+i);
a[i]=t[i]/(1-p[i]);
}
for(i=0;i<=n;i++)
f[i]=i,l[i]=i,r[i]=i,nx[i]=-1,e[i]=0;
for(i=1;i<=n;i++)
Q.push(make_pair(-a[i],i));
while(!Q.empty()){
i=Q.top().second;
Q.pop();
if(e[i])
continue;
e[i]=1;
mrg(b[i],i);
}
for(i=nx[0];i>=0;i=nx[i])
printf("%d\n",i);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5612kb
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: 0ms
memory: 7800kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 4 1 3
result:
wrong answer your plan is not optimal