UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201950#3503. 挑战关卡mikefeng1002011ms46956kbC++112.3kb2024-02-08 12:50:322024-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;
}

Details

小提示:点击横条可展开更详细的信息

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