QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#175553 | #6561. Fail Fast | SolitaryDream# | WA | 1ms | 5968kb | C++17 | 1.1kb | 2023-09-10 19:34:50 | 2023-09-10 19:34:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1e3+7;
struct P{
double t,p;
int id;
}w[N];
bool operator <(const P &a,const P &b)
{
if(a.t+b.t*a.p<b.t+a.t*b.p)
return 1;
if(a.t+b.t*a.p>b.t+a.t*b.p)
return 0;
return a.id<b.id;
}
P operator +(const P &a,const P &b)
{
return {a.t/a.p+b.t,a.p*b.p,a.id};
}
set<P>q;
int n;
int fa[N],p[N],nx[N],t[N];
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
P a;
scanf("%lf%lf",&a.t,&a.p);
a.id=i;
scanf("%d",&p[i]);
fa[i]=i;
q.insert(a);
w[i]=a;
t[i]=i;
}
while(q.size())
{
auto g=*q.begin();
q.erase(q.begin());
int gp=find(g.id),fp=find(p[g.id]);
fa[gp]=fp;
if(fp)
q.erase(w[fp]);
w[fp]=w[fp]+w[gp];
nx[t[fp]]=g.id;
t[fp]=t[gp];
if(fp)
q.insert(w[fp]);
}
for(int i=nx[0];i;i=nx[i])
printf("%d\n",i);
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5968kb
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: 5892kb
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