ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201950 | #3503. 挑战关卡 | mikefeng | 100 | 2011ms | 46956kb | C++11 | 2.3kb | 2024-02-08 12:50:32 | 2024-02-08 13:15:16 |
answer
bool M1;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<iomanip>
#include<cassert>
#include<random>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<map>
#include<set>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
//#include<ext/pb_ds/priority_queue.hpp>
#define fi first
#define se second
#define ll long long
#define Vector Point
#define I128 __int128
#define LD long double
#define ull unsigned ll
#define pii pair<int,int>
#define pb(x) push_back(x)
#define syt cerr<<"sytakioi\n"
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define rd_i(l,r) uniform_int_distribution<int>(l,r)(rd)
#define rd_r(l,r) uniform_real_distribution<double>(l,r)(rd)
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
using namespace std;
//using namespace __gnu_cxx;
mt19937 rd(time(0));
const int N=1e5+5;
int n;
int c[N],fa[N];
LD p[N],ans;
vector<int> e[N];
struct node{
LD c,p;int id;
node(LD _c,LD _p,int _i):c(_c),p(_p),id(_i){}
bool operator < (const node &x)const{return c+p*x.c==x.c+x.p*c?x.id<id:c+p*x.c>x.c+x.p*c;}
bool operator == (const node &x)const{return c==x.c&&p==x.p&&id==x.id;}
};
int id[N];
priority_queue<node> q[N];
inline void merge(int &x,int &y){
if(q[x].size()<q[y].size()) swap(x,y);
while(!q[y].empty()) q[x].emplace(q[y].top()),q[y].pop();
}
inline void dfs(int u){
id[u]=u;
for(int v:e[u]) dfs(v),merge(id[u],id[v]);
if(u){
LD C=0,P=1;
while(!q[id[u]].empty()&&node(c[u]+p[u]*C,p[u]*P,u)<q[id[u]].top()){
node x=q[id[u]].top();q[id[u]].pop();
C+=P*x.c;P*=x.p;
}
q[id[u]].emplace(c[u]+p[u]*C,p[u]*P,u);
}
}
bool M2;
int main(){
int Time=clock();
look_memory;
// freopen("data20.in","r",stdin);
// freopen("1.out","w",stdout);
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
F(i,1,n) cin>>c[i]>>p[i]>>fa[i],e[fa[i]].emplace_back(i);
dfs(0);
LD C=0,P=1;
while(!q[id[0]].empty()){
node x=q[id[0]].top();q[id[0]].pop();
// cout<<x.c<<' '<<x.p<<' '<<x.id<<'\n';
C+=P*x.c;P*=x.p;
}
cout<<fixed<<setprecision(9)<<C<<'\n';
look_time;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 6880kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
107.652312800
result:
ok answer is 107.6523128000
Test #2:
score: 0
Accepted
time: 0ms
memory: 6876kb
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.099341421
result:
ok answer is 29.0993414208
Test #3:
score: 0
Accepted
time: 0ms
memory: 6880kb
input:
5 10 0.5 0 1 0.5 1 1 0.5 1 9 0.5 0 1 0.5 4
output:
11.937500000
result:
ok answer is 11.9375000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 6864kb
input:
1 10 0.5 0
output:
10.000000000
result:
ok answer is 10.0000000000
Test #5:
score: 0
Accepted
time: 3ms
memory: 6880kb
input:
2 100 0.8 0 200 0.7 0
output:
260.000000000
result:
ok answer is 260.0000000000
Test #6:
score: 0
Accepted
time: 3ms
memory: 6868kb
input:
2 10 0.5 0 5 0.4 1
output:
12.500000000
result:
ok answer is 12.5000000000
Test #7:
score: 0
Accepted
time: 3ms
memory: 6864kb
input:
2 1000 0.7 2 1 0.6 0
output:
601.000000000
result:
ok answer is 601.0000000000
Subtask #2:
score: 20
Accepted
Test #8:
score: 20
Accepted
time: 0ms
memory: 6880kb
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.790790270
result:
ok answer is 39.7907902704
Test #9:
score: 0
Accepted
time: 3ms
memory: 6884kb
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.914839450
result:
ok answer is 1009925.9148394496
Test #10:
score: 0
Accepted
time: 0ms
memory: 6884kb
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.982243146
result:
ok answer is 577.9822431460
Test #11:
score: 0
Accepted
time: 0ms
memory: 6880kb
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.922550476
result:
ok answer is 10267758.9225504752
Subtask #3:
score: 10
Accepted
Test #12:
score: 10
Accepted
time: 81ms
memory: 40832kb
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.219794329
result:
ok answer is 4694737.2197943293
Test #13:
score: 0
Accepted
time: 95ms
memory: 46956kb
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.606875223
result:
ok answer is 1006792.6068752232
Test #14:
score: 0
Accepted
time: 135ms
memory: 40828kb
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.220343378
result:
ok answer is 429991141.2203433514
Subtask #4:
score: 15
Accepted
Test #15:
score: 15
Accepted
time: 109ms
memory: 20712kb
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.329885066
result:
ok answer is 40.3298850663
Test #16:
score: 0
Accepted
time: 96ms
memory: 20712kb
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.384330085
result:
ok answer is 25.3843300850
Test #17:
score: 0
Accepted
time: 140ms
memory: 20712kb
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.701757027
result:
ok answer is 273.7017570270
Subtask #5:
score: 55
Accepted
Test #18:
score: 55
Accepted
time: 136ms
memory: 24404kb
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.212088970
result:
ok answer is 1110679.2120889705
Test #19:
score: 0
Accepted
time: 151ms
memory: 25872kb
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.338703736
result:
ok answer is 1624576.3387037360
Test #20:
score: 0
Accepted
time: 152ms
memory: 24384kb
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.844432588
result:
ok answer is 2633368.8444325877
Test #21:
score: 0
Accepted
time: 120ms
memory: 28784kb
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.470317750
result:
ok answer is 3665641.4703177498
Test #22:
score: 0
Accepted
time: 4ms
memory: 6900kb
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.954389966
result:
ok answer is 519.9543899658
Test #23:
score: 0
Accepted
time: 153ms
memory: 35128kb
input:
100000 991626 0.995651 9504 995771 0.998261 79562 998060 0.995175 92360 992097 0.995626 3344 991954 ...
output:
201547094.714379880
result:
ok answer is 201547094.7143798769
Test #24:
score: 0
Accepted
time: 159ms
memory: 40396kb
input:
100000 994360 0.971872 88920 993564 0.952659 41443 987411 0.953086 14489 985630 0.966869 48952 99907...
output:
19644157.969901695
result:
ok answer is 19644157.9699016958
Test #25:
score: 0
Accepted
time: 156ms
memory: 34424kb
input:
100000 985815 0.968338 16495 994819 0.979029 23173 991468 0.983509 81133 982365 0.950143 16314 98305...
output:
1743259885.732734567
result:
ok answer is 1743259885.7327346802
Test #26:
score: 0
Accepted
time: 114ms
memory: 21972kb
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.503918830
result:
ok answer is 76.5039188304
Test #27:
score: 0
Accepted
time: 122ms
memory: 26780kb
input:
100000 210466 0.747974 14014 875274 0.741805 83670 213751 0.306945 37859 924462 0.720568 6619 216870...
output:
214486.483488050
result:
ok answer is 214486.4834880502
Test #28:
score: 0
Accepted
time: 76ms
memory: 13208kb
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.278751152
result:
ok answer is 4122.2787511521