QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131293 | #6561. Fail Fast | installb | WA | 0ms | 6660kb | C++14 | 1.3kb | 2023-07-26 21:03:53 | 2023-07-26 21:03:54 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
typedef double db;
const int N=1e5+10;
int n,nxt[N],f[N],p[N];
struct node{
db c,p;int u,l,r;
node(db _c=0,db _p=0):c(_c),p(_p){}
}a[N];
inline bool operator <(node a,node b){
db t1=a.c/(1-a.p),t2=b.c/(1-b.p);
return t1==t2?a.u<b.u:t1<t2;
// a.c/(1-a.p)<b.c/(1-b.p);
}
set<node> s;
int gfa(int x){return f[x]^x?x=gfa(f[x]):x;}
void merge(int x,int y){
f[x]=y;
nxt[a[y].r]=a[x].l;
a[y].r=a[x].r;
db nc=a[y].c+a[x].c*a[y].p,np=a[x].p*a[y].p;
a[y].c=nc;a[y].p=np;
s.insert(a[y]);
}
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%lf%lf%d",&a[i].c,&a[i].p,&p[i]),a[i].u=a[i].l=a[i].r=i,nxt[i]=0;
rep(i,1,n){
f[i]=i,s.insert(a[i]);
}
int l=0,r=0;
while(!s.empty()){
node t=*s.begin();int x=t.u;
s.erase(s.begin());
int y=gfa(p[x]);
if(!y){
nxt[r]=t.l;
r=t.r;
f[x]=0;
}
else{
f[x]=y;s.erase(s.find(a[y]));
merge(x,y);
}
std::cerr << x << std::endl;
}
// for(int i=nxt[0];i;i=nxt[i]) printf("%d\n",i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 6660kb
input:
4 100 0.5 0 200 0.1 1 10 0.5 2 10 0.9 0
output:
result:
wrong output format Unexpected end of file - int32 expected