QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132500#6561. Fail FastSorting#WA 2ms8648kbC++1.4kb2023-07-30 01:16:382023-07-30 01:16:40

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-30 01:16:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8648kb
  • [2023-07-30 01:16:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
int n;
ld len[100001],pass[100001];
int boss[100001];
int par[100001];
int find(int x){
	if(par[x]!=x) par[x]=find(par[x]);
	return par[x];
}

int rnk[100001];
vector<int>ch[100001];
int ans[100005];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n;
	pass[0]=1;
	for(int i=1; i<=n ;i++){
		/*double x;
		int cur;
		scanf("%d%f%d",&cur,&x,&boss[i]);
		pass[i]=x;
		par[i]=i;
		len[i]=cur;*/
		cin >> len[i] >> pass[i] >> boss[i];
		ch[boss[i]].push_back(i);
	}
	auto cmp = [](int a, int b) { 
		auto resa=len[a]+pass[a]*len[b];
		auto resb=len[b]+pass[b]*len[a];
		if(resa!=resb) return resa<resb;
		else return a<b;
	};
	set<int, decltype(cmp)> s(cmp);
	for(int i=1; i<=n ;i++) s.insert(i);
	for(int i=1; i<=n ;i++){
		int x=*s.begin();s.erase(s.begin());
		rnk[x]=i;
		int y=find(boss[x]);
		if(y!=0) s.erase(y);
		len[y]=len[y]+pass[y]*len[x];
		pass[y]=pass[y]*pass[x];
		par[x]=y;
		if(y!=0) s.insert(y);
	}
	typedef pair<int,int> pii;
	priority_queue<pii,vector<pii>,greater<pii> >pq;
	int ptr=0;
	for(auto c:ch[0]) pq.push({rnk[c],c});
	while(!pq.empty()){
		auto tmp=pq.top();pq.pop();
		ans[++ptr]=tmp.se;
		for(auto c:ch[tmp.se]) pq.push({rnk[c],c});
	}
	for(int i=1; i<=n ;i++) cout << ans[i] << '\n';
}

詳細信息

Test #1:

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

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: 8648kb

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