QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689558 | #9532. 长野原龙势流星群 | ANIG | 10 | 970ms | 17980kb | C++14 | 683b | 2024-10-30 17:44:11 | 2024-10-30 17:44:13 |
Judging History
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%