QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#132499 | #6561. Fail Fast | Sorting# | RE | 0ms | 0kb | C++ | 1.4kb | 2023-07-30 01:16:15 | 2023-07-30 01:16:17 |
Judging History
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]);
}
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: 0
Runtime Error
input:
4 100 0.5 0 200 0.1 1 10 0.5 2 10 0.9 0