QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235284#6561. Fail Fastugly2333WA 1ms7800kbC++20923b2023-11-02 16:55:552023-11-02 16:55:55

Judging History

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

  • [2023-11-02 16:55:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7800kb
  • [2023-11-02 16:55:55]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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