UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#201928#3503. 挑战关卡yllcm1001445ms6428kbC++111.3kb2024-02-08 09:57:492024-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