QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689558#9532. 长野原龙势流星群ANIG10 970ms17980kbC++14683b2024-10-30 17:44:112024-10-30 17:44:13

Judging History

你现在查看的是最新测评结果

  • [2024-10-30 17:44:13]
  • 评测
  • 测评结果:10
  • 用时:970ms
  • 内存:17980kb
  • [2024-10-30 17:44:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,fa[N],w[N],mk[N];
vector<int>p[N];
double f[N],nw;
bool cmp(int a,int b){
	return f[a]>f[b];
}
void dfs(int x){
	mk[x]=1;
	f[x]=w[x]-nw;
	for(auto c:p[x]){
		if(mk[c])continue;
		dfs(c);
		if(f[c]>0)f[x]+=f[c];
	}
	mk[x]=0;
}
signed main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		scanf("%lld",&fa[i]);
		p[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	for(int i=1;i<=n;i++){
		double l=0,r=1e9;
		for(int j=1;j<=50;j++){
			double mid=(l+r)/2;
			nw=mid;
			dfs(i);
			if(f[i]>=0)l=mid;
			else r=mid;
		}
		printf("%.10lf\n",l);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 10
Accepted
time: 7ms
memory: 14172kb

input:

2000
1 2 2 4 5 2 3 6 4 2 7 2 8 14 8 12 1 14 4 14 8 18 9 2 7 22 20 22 14 29 28 16 6 21 23 6 21 14 13 9 1 4 18 13 2 39 21 33 18 20 38 27 27 1 49 5 51 3 31 24 10 42 2 44 13 9 35 66 27 60 67 59 29 40 53 2 33 43 26 43 62 16 78 45 14 10 73 69 41 35 25 26 2 70 54 1 54 48 5 36 44 28 90 29 51 51 93 82 95 45 ...

output:

883838885.9230761528
887174925.9999992847
881025216.7096769810
912609654.6666665077
872318573.4999995232
831791515.1538457870
867874849.9999997616
892392319.1666665077
836427215.9999997616
869519853.7999998331
693335785.3750000000
925100889.9999995232
994728511.4999998808
950304718.9999998808
808673...

result:

ok 2000 numbers

Test #2:

score: 10
Accepted
time: 3ms
memory: 14116kb

input:

2000
1 1 1 1 1 6 6 6 8 1 7 6 9 4 11 10 17 1 9 20 4 2 7 22 13 21 5 26 19 20 9 8 24 22 32 24 24 8 30 7 22 22 7 14 4 18 30 38 9 45 21 38 53 16 39 6 44 12 10 34 14 17 54 14 65 55 17 21 40 9 27 65 54 53 61 30 3 52 57 49 31 34 16 32 11 85 81 43 36 43 3 45 42 93 83 37 86 77 2 23 41 77 19 18 51 91 68 22 85 ...

output:

794920955.2199993134
713825019.5000000000
734115991.7999994755
800547209.7837829590
734508346.9999992847
760946433.3749996424
750093634.8979587555
735976830.1111105680
765501191.9411761761
747665901.9523806572
816306482.5000000000
741938108.1111104488
790936468.7499997616
784791287.9047616720
686615...

result:

ok 2000 numbers

Test #3:

score: 10
Accepted
time: 6ms
memory: 14236kb

input:

2000
1 1 2 3 3 3 3 4 2 8 4 6 2 10 1 8 8 13 1 19 15 18 8 17 20 16 16 21 11 28 14 18 31 4 30 24 17 10 22 26 2 34 14 13 13 37 43 3 3 38 9 4 29 43 29 46 7 55 9 23 23 49 29 12 45 25 67 59 45 24 5 55 52 73 51 28 25 26 49 78 62 10 18 1 35 73 35 16 52 62 5 89 4 49 12 46 55 14 18 68 64 25 21 88 25 19 82 46 4...

output:

755177543.5161287785
762060513.2941172123
754126791.2624993324
777333185.5499999523
758703127.4999995232
756576527.2222213745
764146306.7857135534
750062914.1399998665
710728919.8124992847
770351278.7499997616
769495170.0000000000
776873566.5714282990
763361472.5999999046
718961316.4545452595
691159...

result:

ok 2000 numbers

Test #4:

score: 10
Accepted
time: 6ms
memory: 12352kb

input:

2000
1 1 3 4 1 1 4 3 3 2 1 3 11 3 1 7 17 9 7 18 4 5 16 10 16 14 12 6 16 22 28 32 27 4 4 19 36 38 12 31 28 18 30 44 35 43 44 29 10 29 7 18 18 35 23 42 12 24 23 2 42 59 8 24 14 49 16 62 38 46 7 34 41 41 10 20 53 71 18 38 63 54 26 76 39 84 28 36 9 53 26 19 39 34 26 49 86 10 64 34 74 43 19 70 97 35 92 4...

output:

914894038.5333333015
918141155.8333332539
911927554.9999992847
870659540.1538460255
777969562.2352937460
778920774.5555551052
876560725.0000000000
974455317.9999995232
858643515.2499996424
835985850.6190474033
963419161.2499992847
868819816.9999995232
813378294.9999997616
984875620.9999997616
762109...

result:

ok 2000 numbers

Test #5:

score: 10
Accepted
time: 3ms
memory: 12140kb

input:

2000
1 2 2 3 2 1 7 8 8 6 9 12 12 3 8 3 9 15 3 19 8 7 4 19 18 23 10 21 10 15 10 22 1 21 19 26 1 38 38 1 18 37 14 27 37 43 30 4 2 2 13 42 13 9 13 38 21 23 58 32 13 62 18 62 15 49 5 61 1 45 29 48 38 34 31 43 45 38 52 54 13 21 78 36 21 45 57 14 25 18 29 45 2 43 8 51 75 79 95 55 29 98 55 93 33 5 93 14 77...

output:

865975765.9540226460
864960665.5999991894
853815173.5555547476
725289681.7999997139
835914002.7499998808
751151162.2999993563
880779494.2631578445
883843482.9166662693
866946310.4599994421
875695250.2727272511
798984107.3999998569
869102654.8928570747
879836598.4166665077
911092097.0000000000
850227...

result:

ok 2000 numbers

Test #6:

score: 10
Accepted
time: 8ms
memory: 12608kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

780031265.2857134342
709196423.6341457367
852016016.9999994040
710198590.8550715446
942523003.9999998808
795582646.9999997616
817131606.9999992847
723247621.6749992371
711787456.3214280605
702698215.8181810379
778948304.7500000000
825829512.6666662693
731540545.6842095852
717838198.7249995470
755917...

result:

ok 2000 numbers

Test #7:

score: 10
Accepted
time: 4ms
memory: 14172kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

621161049.0487799644
460347579.9461537600
624970425.7239258289
386751620.2403100729
463913107.3178291321
565084289.9534883499
628866372.3798445463
344826388.1999995708
389755854.0156245232
428515994.7968750000
467520113.5312495828
517598544.1640618443
569478380.3046875000
614133627.3046871424
633756...

result:

ok 2000 numbers

Test #8:

score: 10
Accepted
time: 2ms
memory: 14176kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

621374004.5748784542
487030122.8749998808
624597241.6999999285
939364019.0000000000
480110389.2480620146
578610052.9999995232
628514468.2138357162
497600201.9999991655
398302285.6701028943
430778150.1788613796
483844086.0234367847
534427093.2698407173
585697877.2592586279
623651552.6739125252
634659...

result:

ok 2000 numbers

Test #9:

score: 10
Accepted
time: 4ms
memory: 12120kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

762088830.2333329916
781353370.1724129915
714336862.8333328962
723995695.1304345131
787379090.4642856121
708370854.0526309013
735529969.8260866404
725933828.3181813955
721088075.7380948067
810402666.8888888359
798070041.7142853737
761321867.9999995232
708379177.7407404184
806707102.9999997616
682416...

result:

ok 2000 numbers

Test #10:

score: 10
Accepted
time: 8ms
memory: 12292kb

input:

2000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 5...

output:

796409562.0000000000
777105384.2499995232
719995401.8399994373
755696351.5238087177
972657379.9999992847
705728479.9464279413
822339463.6666662693
756514023.7142848969
858700662.9999995232
980362468.0000000000
924539106.0000000000
708454242.9999995232
722158127.3103439808
856914922.9999996424
691671...

result:

ok 2000 numbers

Test #11:

score: 10
Accepted
time: 0ms
memory: 14188kb

input:

2000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

984618295.6153841019
902277196.9999992847
383235588.9999998808
742640715.9999994040
613666672.0000000000
291453149.9999998212
625937042.9999995232
958739024.9999997616
34831726.9999993742
240997072.9999999404
334863695.9999994040
223278813.9999995232
111864226.9999998659
669195135.9999997616
1725111...

result:

ok 2000 numbers

Test #12:

score: 0
Time Limit Exceeded

input:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

output:

506787773.3134319782
507473433.6541348696
508859284.1666663885
556160454.2499996424
620472531.0000000000
867793535.9999997616
786222332.9999995232
511025497.6808504462
532981265.4285709858
612986219.9999997616
767631955.6666665077
992646283.9999992847
966889609.0000000000
550282737.3333332539
558374...

result:


Subtask #2:

score: 10
Accepted

Test #32:

score: 10
Accepted
time: 964ms
memory: 17884kb

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

792545632.4154920578
794937150.3513510227
794843085.4776118994
804131414.2264149189
805846267.1666666269
806376229.9999996424
778037203.6904761791
815562308.1499996185
776087995.6012649536
809328819.5882344246
767722826.5953752995
771619640.6969695091
800107654.4769228697
879639965.3333325386
775670...

result:

ok 200000 numbers

Test #33:

score: 10
Accepted
time: 830ms
memory: 17956kb

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

647279839.4787683487
635973895.0667315722
647532087.5491032600
520992591.3328454494
636283816.4230017662
647784525.8479523659
406566953.6435878873
463185839.5329101086
521246596.0463186502
578740922.6221351624
636594030.4714766741
648037157.7063177824
350728412.3924049139
378574282.5988309979
406857...

result:

ok 200000 numbers

Test #34:

score: 10
Accepted
time: 847ms
memory: 17980kb

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

647754328.6135559082
636746616.8528261185
648006765.7346060276
521510675.0136513114
637057064.1545586586
648259391.9438591003
406874686.2233050466
464547475.6857135296
521775592.6519478559
579595626.9678041935
637367808.8653651476
648512210.6579561234
351934818.7283349037
380442260.0379746556
407073...

result:

ok 200000 numbers

Test #35:

score: 10
Accepted
time: 885ms
memory: 17944kb

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

645282008.9919056892
637131985.0808169842
645927540.9527158737
532495411.9310340881
637752960.4493173361
646578004.8590126038
427748181.9099992514
483202190.8700694442
532964564.7483287454
595909324.7582690716
638382656.9920704365
647229761.6673384905
387662294.1428564787
423468034.9999999404
428200...

result:

ok 200000 numbers

Test #36:

score: 10
Accepted
time: 970ms
memory: 17948kb

input:

200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...

output:

786262518.9269658327
780254007.0479996204
788435954.4367079735
771824213.5253455639
791202439.0967741013
796752745.7499992847
792549624.9646010399
776723747.1851843596
771848261.4579434395
795200761.5999994278
766509591.2608695030
773506193.3529411554
798299194.9999992847
797955826.4095230103
743353...

result:

ok 200000 numbers

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #3:

0%