ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201928 | #3503. 挑战关卡 | yllcm | 100 | 1445ms | 6428kb | C++11 | 1.3kb | 2024-02-08 09:57:49 | 2024-02-08 13:12:56 |
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = 0;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 1e5 + 10;
int n;
int par[N], f[N], cnt[N];
struct Node {db c, p;}a[N];
bool operator < (Node x, Node y) {
return x.c + y.c * x.p > y.c + x.c * y.p;
}
Node operator + (Node x, Node y) {
return {x.c + x.p * y.c, x.p * y.p};
}
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
int main() {
n = read();
priority_queue<pair<Node, pair<int, int>>> q;
a[0] = {0, 1};
for(int i = 1; i <= n; i++) {
int d; db c, p;
scanf("%lf%lf%d", &c, &p, &d);
par[i] = d; f[i] = i; a[i] = {c, p};
q.push({a[i], {i, 0}});
}
while(q.empty() == false) {
auto x = q.top(); q.pop();
if(x.SE.SE != cnt[x.SE.FR])continue;
int u = x.SE.FR, p = find(par[u]);
a[p] = a[p] + a[u]; f[u] = par[u];
if(p)cnt[p]++, q.push({a[p], {p, cnt[p]}});
}
printf("%.10lf\n", a[0].c);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 1300kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
107.6523128000
result:
ok answer is 107.6523128000
Test #2:
score: 0
Accepted
time: 0ms
memory: 1308kb
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...
output:
29.0993414208
result:
ok answer is 29.0993414208
Test #3:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
5 10 0.5 0 1 0.5 1 1 0.5 1 9 0.5 0 1 0.5 4
output:
11.9375000000
result:
ok answer is 11.9375000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 1296kb
input:
1 10 0.5 0
output:
10.0000000000
result:
ok answer is 10.0000000000
Test #5:
score: 0
Accepted
time: 0ms
memory: 1300kb
input:
2 100 0.8 0 200 0.7 0
output:
260.0000000000
result:
ok answer is 260.0000000000
Test #6:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
2 10 0.5 0 5 0.4 1
output:
12.5000000000
result:
ok answer is 12.5000000000
Test #7:
score: 0
Accepted
time: 0ms
memory: 1296kb
input:
2 1000 0.7 2 1 0.6 0
output:
601.0000000000
result:
ok answer is 601.0000000000
Subtask #2:
score: 20
Accepted
Test #8:
score: 20
Accepted
time: 0ms
memory: 1308kb
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...
output:
39.7907902704
result:
ok answer is 39.7907902704
Test #9:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
20 971329 0.076234 0 996879 0.012978 0 994191 0.056803 0 978400 0.080792 1 907508 0.008858 4 992071 ...
output:
1009925.9148394496
result:
ok answer is 1009925.9148394496
Test #10:
score: 0
Accepted
time: 0ms
memory: 1304kb
input:
20 54 0.952741 0 41 0.912397 0 11 0.963309 0 66 0.915806 3 47 0.919191 4 51 0.906473 5 24 0.989650 6...
output:
577.9822431460
result:
ok answer is 577.9822431460
Test #11:
score: 0
Accepted
time: 1ms
memory: 1304kb
input:
20 933154 0.904059 0 929160 0.911627 0 999437 0.921760 0 991335 0.904136 1 903530 0.943148 4 904464 ...
output:
10267758.9225504734
result:
ok answer is 10267758.9225504752
Subtask #3:
score: 10
Accepted
Test #12:
score: 10
Accepted
time: 108ms
memory: 6424kb
input:
100000 938188 0.740681 0 575610 0.965656 1 937341 0.842524 2 817797 0.945396 3 602563 0.818956 4 893...
output:
4694737.2197943302
result:
ok answer is 4694737.2197943293
Test #13:
score: 0
Accepted
time: 54ms
memory: 6424kb
input:
100000 501234 0.500516 0 501214 0.503354 1 501013 0.504058 2 502546 0.502962 3 500273 0.505433 4 500...
output:
1006792.6068752231
result:
ok answer is 1006792.6068752232
Test #14:
score: 0
Accepted
time: 152ms
memory: 6428kb
input:
100000 768956 0.999996 0 686063 0.999982 1 817790 0.999964 2 897069 0.999958 3 940413 0.999956 4 879...
output:
429991141.2203430533
result:
ok answer is 429991141.2203433514
Subtask #4:
score: 15
Accepted
Test #15:
score: 15
Accepted
time: 60ms
memory: 6040kb
input:
100000 878369 0.541257 0 958147 0.398813 0 358636 0.233155 0 298088 0.094053 0 263689 0.781900 0 551...
output:
40.3298850663
result:
ok answer is 40.3298850663
Test #16:
score: 0
Accepted
time: 67ms
memory: 6040kb
input:
99877 384696 0.022932 0 303896 0.134365 0 419701 0.126965 0 687491 0.253655 0 119116 0.220182 0 6586...
output:
25.3843300850
result:
ok answer is 25.3843300850
Test #17:
score: 0
Accepted
time: 75ms
memory: 6044kb
input:
99979 640809 0.767636 0 18778 0.998922 0 696336 0.525512 0 738866 0.867968 0 257693 0.707216 0 17851...
output:
273.7017570270
result:
ok answer is 273.7017570270
Subtask #5:
score: 55
Accepted
Test #18:
score: 55
Accepted
time: 85ms
memory: 6428kb
input:
100000 686602 0.755750 0 606835 0.951986 0 713656 0.504635 0 609527 0.663061 0 752558 0.613758 0 997...
output:
1110679.2120889709
result:
ok answer is 1110679.2120889705
Test #19:
score: 0
Accepted
time: 87ms
memory: 6424kb
input:
100000 866461 0.563475 0 566909 0.892585 1 794999 0.608805 1 572103 0.501998 1 889513 0.669248 4 712...
output:
1624576.3387037362
result:
ok answer is 1624576.3387037360
Test #20:
score: 0
Accepted
time: 91ms
memory: 6424kb
input:
100000 724633 0.992242 0 519908 0.739362 1 841119 0.933434 2 791058 0.900611 3 675619 0.998138 4 764...
output:
2633368.8444325882
result:
ok answer is 2633368.8444325877
Test #21:
score: 0
Accepted
time: 98ms
memory: 6428kb
input:
100000 526633 0.902698 0 515821 0.957942 1 871718 0.810818 2 920847 0.633590 3 826181 0.806362 4 876...
output:
3665641.4703177498
result:
ok answer is 3665641.4703177498
Test #22:
score: 0
Accepted
time: 0ms
memory: 1308kb
input:
100 456 0.123000 44 456 0.123000 0 456 0.123000 9 456 0.123000 10 456 0.123000 95 456 0.123000 100 4...
output:
519.9543899658
result:
ok answer is 519.9543899658
Test #23:
score: 0
Accepted
time: 97ms
memory: 6428kb
input:
100000 991626 0.995651 9504 995771 0.998261 79562 998060 0.995175 92360 992097 0.995626 3344 991954 ...
output:
201547094.7143797278
result:
ok answer is 201547094.7143798769
Test #24:
score: 0
Accepted
time: 90ms
memory: 6428kb
input:
100000 994360 0.971872 88920 993564 0.952659 41443 987411 0.953086 14489 985630 0.966869 48952 99907...
output:
19644157.9699016847
result:
ok answer is 19644157.9699016958
Test #25:
score: 0
Accepted
time: 103ms
memory: 6428kb
input:
100000 985815 0.968338 16495 994819 0.979029 23173 991468 0.983509 81133 982365 0.950143 16314 98305...
output:
1743259885.7327365875
result:
ok answer is 1743259885.7327346802
Test #26:
score: 0
Accepted
time: 82ms
memory: 6428kb
input:
100000 379221 0.374168 0 219097 0.093397 0 141258 0.041142 0 773286 0.353950 0 479988 0.960409 0 169...
output:
76.5039188304
result:
ok answer is 76.5039188304
Test #27:
score: 0
Accepted
time: 102ms
memory: 6428kb
input:
100000 210466 0.747974 14014 875274 0.741805 83670 213751 0.306945 37859 924462 0.720568 6619 216870...
output:
214486.4834880502
result:
ok answer is 214486.4834880502
Test #28:
score: 0
Accepted
time: 93ms
memory: 6424kb
input:
99856 576549 0.545246 0 430801 0.958125 0 987874 0.848851 0 783119 0.204964 0 855730 0.750672 0 3106...
output:
4122.2787511521
result:
ok answer is 4122.2787511521