QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#491106 | #6561. Fail Fast | SmallAoPigBigPiPig# | WA | 11ms | 42748kb | C++23 | 1.4kb | 2024-07-25 17:15:43 | 2024-07-25 17:15:44 |
Judging History
answer
#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Max(a, b) ((a) > (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int ch = 0, f = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 1000005;
int nxt[N], lst[N], pa[N], vis[N], n;
struct node{
long double p, c;
inline node(){ p = c = 0; }
inline node(long double _p, long double _c){
p = _p, c = _c;
}
} a[N];
bool operator < (node a, node b){
return a.c * (1 - b.p) > b.c * (1 - a.p);
}
node operator + (node a, node b){
return node(a.p * b.p, a.c + a.p * b.c);
}
priority_queue<pair<node, int> > pq;
#define fi first
#define se second
inline void output(int x){
for(; x; x = nxt[x]) printf("%d\n", x);
}
int main(){
read(n);
for(int i = 1; i <= n; i++){
long double c, p; int f;
scanf("%Lf%Lf%d", &c, &p, &f);
pa[i] = f, a[i] = node(p, c);
pq.push(make_pair(a[i], i));
lst[i] = i;
}
vis[0] = 1;
while(!pq.empty()){
auto [x, y] = pq.top();
pq.pop();
if(vis[y]) continue;
vis[y] = 1;
if(vis[pa[y]]) output(y);
else{
nxt[lst[pa[y]]] = y;
lst[pa[y]] = y;
pq.push(make_pair(a[pa[y]] + x, pa[y]));
a[pa[y]] = a[pa[y]] + x;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 41920kb
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: 0
Accepted
time: 11ms
memory: 42552kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 1 3 4
result:
ok correct
Test #3:
score: 0
Accepted
time: 7ms
memory: 42748kb
input:
10 18 0.574073 0 13 0.540309 0 13 0.539018 2 12 0.572910 2 15 0.570616 4 16 0.510215 3 17 0.504083 5 19 0.539297 1 19 0.577271 7 10 0.578346 1
output:
2 4 3 6 5 7 1 10 8 9
result:
ok correct
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 41968kb
input:
20 93 0.093030 0 53 0.056639 0 39 0.021549 0 48 0.069268 3 58 0.009572 4 22 0.015083 1 27 0.024351 5 68 0.085055 7 48 0.031563 5 46 0.025067 9 15 0.095445 2 57 0.011233 6 97 0.028239 2 8 0.060758 6 59 0.097330 13 34 0.052120 3 73 0.055127 11 53 0.004135 12 24 0.051183 5 56 0.027001 13
output:
3 16 4 2 11 12 18 5 19 7 9 10 8 17 1 6 14 13 20 15
result:
wrong answer Test 12 wrongly executed before test 6.