QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131293#6561. Fail FastinstallbWA 0ms6660kbC++141.3kb2023-07-26 21:03:532023-07-26 21:03:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-26 21:03:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:6660kb
  • [2023-07-26 21:03:53]
  • 提交

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