QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165686#6561. Fail FastPhantomThreshold#WA 2ms12584kbC++201.4kb2023-09-05 20:47:302023-09-05 20:47:31

Judging History

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

  • [2023-09-05 20:47:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12584kb
  • [2023-09-05 20:47:30]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
//define int long long
using namespace std;

const int maxn = 210000;

int par[maxn],fa[maxn];
int findfa(const int x){ return fa[x]==x?x:fa[x]=findfa(fa[x]); }

struct node
{
	int i,id;
	double p,t;
	friend inline bool operator <(const node &k1,const node &k2)
	{
		return k1.t/k1.p > k2.t/k2.p;
	}
}a[maxn];
int id[maxn],cnt;
int n, vis[maxn];

priority_queue< node > q;
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > >Q;

vector<int>V[maxn];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	a[0].p=1; a[0].t=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].t>>a[i].p;
		a[i].p= 1-a[i].p;
		int x; cin>>x; par[i]=x;
		V[x].push_back(i);
	}
	
	for(int i=0;i<=n;i++) fa[i]=i;
	
	cnt=n;
	for(int i=1;i<=n;i++)
	{
		id[i]=i;
		a[i].i=i;
		a[i].id=i;
		
		q.push(a[i]);
	}
	
	int ord=0;
	while(!q.empty())
	{
		const node temp= q.top(); q.pop();
		int i=temp.i;
		if( id[i]!=temp.id ) continue;
		int j=findfa(par[i]);
		
		a[j].t= a[j].t+ (1-a[j].p)*a[i].t;
		a[j].p= 1- (1-a[j].p)*(1-a[i].p);
		id[j]=a[j].id=++cnt;
		if(par[j]) q.push( a[j] );
		
		fa[i]=j;
		vis[i]=++ord;
	}
	
	for(int i=1;i<=n;i++) if(par[i]==0)
		Q.emplace( vis[i],i );
	
	while(!Q.empty())
	{
		const auto [vs,i] = Q.top(); Q.pop();
		cout<<i<<'\n';
		for(auto j:V[i])
			Q.emplace( vis[j],j );
	}
	
	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 12584kb

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: 2ms
memory: 10904kb

input:

4
84 0.716 0
91 0.115 0
19 0.640 1
103 0.455 0

output:

1
3
2
4

result:

wrong answer your plan is not optimal