QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556666 | #9238. Tree | Xun_xiaoyao | 17 | 57ms | 26004kb | C++17 | 998b | 2024-09-10 20:05:13 | 2024-09-10 20:05:13 |
Judging History
answer
#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
int fa[200010];
int get_fa(int a){return a==fa[a]?a:fa[a]=get_fa(fa[a]);}
int n,w[200010],siz[200010];
vector<int> son[200010],nd;
long long ccf[200010],cf[200010],f[200010];
void init(std::vector<int> P, std::vector<int> W)
{
n=W.size();
for(int i=2;i<=n;i++) son[P[i-1]+1].push_back(i);
for(int i=1;i<=n;i++) w[i]=W[i-1];
for(int i=1;i<=n;i++)
{
if(son[i].empty()) f[n+2]+=w[i];
else nd.push_back(i);
fa[i]=i,siz[i]=1;
}
sort(nd.begin(),nd.end(),[&](int a,int b){return w[a]>w[b];});
for(int g:nd)
{
int u=get_fa(g);
if(u==1) ccf[siz[1]]-=w[g];
siz[u]--;
for(int v:son[g])
{
fa[v]=u,siz[u]+=siz[v];
ccf[siz[v]]+=w[v]-w[g],ccf[1]-=w[v]-w[g];
}
if(u==1) ccf[siz[1]]+=w[g];
}
for(int i=n+1;i;i--) cf[i]=cf[i+1]+ccf[i];
for(int i=n+1;i;i--) f[i]=f[i+1]+cf[i];
}
long long query(int L, int R)
{
int k=min(R/L,n);
return f[k+2]*L+cf[k+1]*(L-R%L);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 23ms
memory: 22680kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 2 2 4 5 4 5 8 9 10 9 8 10 14 15 14 15 18 19 20 21 18 22 21 24 24 27 22 27 30 31 31 33 30 19 20 33 38 38 40 41 41 43 44 43 44 47 48 49 50 49 50 53 54 53 48 54 58 58 60 60 62 62 64 64 66 66 67 67 70 71 72 71 72 75 70 75 78 78 80 81 80 81 84 85 86 86 88 89 90...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 682654248246 834059146585 104107877065 626344246917 578222335946 1248276814116 1306128583094 417838861293 365718115496 1302019336262
result:
ok
Test #2:
score: 10
Accepted
time: 26ms
memory: 22532kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 2 2 4 5 6 7 7 9 9 11 12 11 5 13 12 6 4 13 20 21 20 21 24 25 25 27 28 27 28 29 32 32 34 35 36 36 37 34 39 41 39 35 37 42 41 42 48 48 50 50 52 52 54 54 56 57 58 58 56 59 59 63 63 65 66 65 57 66 70 70 72 73 73 75 72 75 78 78 80 80 81 83 83 84 81 29 24 84 90 9...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 2412828 1922117 1327147 965330 1085799 1564240 1690944 1688948 2415056 1441542
result:
ok
Test #3:
score: 10
Accepted
time: 31ms
memory: 20744kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 0 3 4 5 4 4 5 5 10 10 10 13 13 15 15 15 18 3 5 5 18 23 24 24 25 27 27 27 27 31 32 33 32 33 33 33 38 38 38 41 41 38 32 38 38 41 48 48 50 50 50 53 53 55 55 55 48 55 60 60 55 61 64 64 64 64 53 64 55 64 72 72 72 50 48 72 78 78 80 81 81 81 81 83 86 86 86 86 88 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 57510536913265758 13893873797083323 19946610899128 612378945455168 5805050629165603 24375661619556703 36105231950324439 45342443221065693 18169686485050308 12956499749658231
result:
ok
Test #4:
score: 10
Accepted
time: 39ms
memory: 22728kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 7 8 9 9 10 12 13 14 14 13 17 15 19 20 21 21 22 22 25 26 27 27 29 30 30 32 32 34 35 36 37 36 38 40 41 42 43 44 38 36 40 48 49 49 51 52 53 53 52 56 57 55 57 59 61 62 63 64 65 66 63 68 69 69 71 67 73 73 74 76 77 76 76 80 80 82 83 80 75 86 77 88 89 9...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 7643905133299046 28184208216232992 397398112600514 439994136720137 32751552084610538 34770551047442984 2746924426773012 1660650876324804 36635310270169815 52687563609961576
result:
ok
Test #5:
score: 10
Accepted
time: 34ms
memory: 22700kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 7 8 9 8 11 12 13 13 12 14 15 18 19 20 21 22 23 24 23 26 27 28 29 30 30 32 31 34 35 36 35 37 37 40 41 42 43 43 45 43 47 48 47 50 51 50 48 54 55 55 57 58 59 59 61 62 61 60 62 52 67 68 69 70 70 72 73 74 71 74 75 78 78 78 78 58 83 46 61 86 73 88 89 8...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 26872827042939935 49372923666359196 9058883871784635 6777056622183544 1838319902044609 32141218683607317 3983594684931644 57790759896735111 27089846953780734 10261160977025592
result:
ok
Test #6:
score: 10
Accepted
time: 29ms
memory: 22912kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 7 8 8 10 11 11 13 14 15 16 17 18 18 20 21 22 22 24 17 23 21 22 29 29 31 32 33 34 31 33 35 38 38 40 41 42 39 44 45 46 46 48 49 38 51 43 53 53 50 56 45 58 58 60 59 60 63 63 64 66 66 68 65 67 71 66 66 72 75 75 77 78 77 80 76 79 83 83 80 86 87 88 89 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 46240945687 75809785349 1427956109 18769152814 10917853217 38913156840 15656876405 40210377091 62339284486 12811886908
result:
ok
Test #7:
score: 10
Accepted
time: 41ms
memory: 22552kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 3 4 6 7 8 9 10 10 12 13 14 11 16 17 18 19 20 21 21 23 24 25 25 27 24 28 30 31 32 28 34 35 36 37 22 29 23 17 31 43 43 45 46 43 48 49 47 51 51 53 46 49 56 57 58 58 60 61 62 57 64 63 66 65 45 69 70 71 72 68 23 75 76 77 73 79 80 81 82 83 84 84 85 87 88 89 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 40918849029853209 7833596601568197 5990593014536811 4352190437322498 17295263219976717 47008068426232620 954287740499985 15897745496652069 22735636717009101 8720508161191782
result:
ok
Test #8:
score: 10
Accepted
time: 41ms
memory: 22540kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 4 6 7 8 8 9 11 12 7 14 15 15 17 16 17 17 21 22 23 17 20 14 25 28 26 30 30 32 33 31 35 36 33 38 35 40 41 41 30 38 45 31 33 48 49 50 51 33 50 53 55 56 56 58 59 60 59 62 63 64 56 66 66 68 62 60 55 62 59 74 74 76 77 77 32 80 81 82 44 58 85 85 85 88 89 89...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 18332177014668621 48287181796568495 21123963074015684 53693699485878843 2086270347806154 51638060827009153 25332123081029950 1389829310508093 14190661594976877 70996135211589918
result:
ok
Test #9:
score: 10
Accepted
time: 40ms
memory: 21728kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 5 4 8 9 10 11 8 9 14 15 16 17 18 17 20 21 10 23 23 25 26 26 28 28 19 31 32 33 31 35 36 33 18 39 40 41 42 40 29 45 46 47 46 49 49 47 45 53 53 54 32 57 57 30 60 61 62 61 64 60 27 67 68 68 70 69 72 71 71 7 11 77 78 79 79 81 78 83 84 85 86 87 87 86 90 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 27482511519482973 54801483810360485 16427935358969097 18858137547390619 77884374862242783 26106356577065893 6900572582069509 10154611289838451 29452407535664386 51588785737271760
result:
ok
Test #10:
score: 10
Accepted
time: 24ms
memory: 19088kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 76294866873700498 93890907422242820 93434331911152132 74666580729163472 52192075803472304 95086795576987856 59809293897104834 53869016712136914 77675882910684380 89712991728300302
result:
ok
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 13
Accepted
time: 3ms
memory: 14216kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 2000 0 0 1 1 4 4 6 7 6 7 10 10 12 12 14 15 14 15 18 19 19 21 18 21 24 24 26 27 26 27 30 30 32 32 34 34 36 37 38 39 39 41 37 38 36 41 46 47 48 47 48 51 51 53 54 54 56 56 58 58 60 61 61 63 64 64 66 67 66 67 70 71 72 72 74 75 76 76 75 74 70 77 63 60 77 85 85 87 87 89 89...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 175909322571 633257447922 815909942751 39651169609 1036267874610 610572524261 164360385196 32373687020 128373030516 267765616314
result:
ok
Test #12:
score: 0
Wrong Answer
time: 2ms
memory: 12108kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 2000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 14 18 16 20 21 22 22 20 25 20 27 28 28 30 29 32 29 34 29 35 29 30 26 40 41 42 41 44 45 46 47 48 49 48 49 49 53 54 54 48 52 55 59 59 61 61 50 64 65 66 64 66 69 70 51 72 72 73 75 76 77 77 78 74 81 82 73 84 74 76 87 87 89 90...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 277179910141240 811317516213416 465020459267822 73864218608949 121132960104990 119132181909903 67730460858186 162761063658871 616249239929798 536849298135591
result:
wrong answer 3rd lines differ - on the 1st token, expected: '127351551273446', found: '277179910141240'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 7
Accepted
Test #33:
score: 7
Accepted
time: 44ms
memory: 23256kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 0 1 2 2 6 6 7 7 10 11 11 13 14 13 14 17 10 17 20 21 22 22 23 21 20 23 28 29 28 29 32 33 34 32 33 34 38 39 39 40 42 42 44 45 46 47 48 45 46 48 52 53 53 54 56 56 58 58 60 61 62 63 63 65 61 66 62 66 70 71 71 72 72 75 60 65 75 79 52 44 70 47 40 54 79 87 87 89 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 18330254280 114566555886 5123993634 1571790384 1390661403 102887513647 12142338294 532135751 48879256279 74804356884 7047438873 58553215238 26812191362 41269971650 32111371952 8116162880 57784940023 106724111433 93322831828 42829869427 28126687591 28123313538 1525...
result:
ok
Test #34:
score: 7
Accepted
time: 38ms
memory: 23244kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 20 23 25 25 27 28 29 29 30 32 33 33 22 36 33 34 39 39 40 42 43 44 45 39 47 48 49 50 51 52 52 54 51 56 57 58 59 60 60 61 62 59 61 66 67 68 63 70 71 68 58 61 75 76 77 66 73 80 60 60 83 83 58 86 87 86 89 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 50233536385 3587514281 5880195973 137570322832 29902093191 26550751346 32639328031 66964630751 25701201292 103130504357 54417568193 90440614687 29659144821 30382916893 3188471716 14164945825 46749986071 1254071200 57249463618 32639228784 26502847608 103554150130 1...
result:
ok
Test #35:
score: 7
Accepted
time: 43ms
memory: 23520kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 16 17 18 19 20 20 22 22 22 24 25 22 28 29 29 29 32 32 32 35 35 37 38 39 38 21 17 41 44 45 30 47 48 48 49 51 52 52 54 55 55 55 50 59 55 54 62 63 64 62 62 64 67 62 59 51 72 73 74 75 76 75 56 79 80 81 80 82 82 85 82 87 88 55 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 44679405666 7344895774 71198961182 21219279009 50500461174 7095602694 60932721243 137763754969 17105320274 37016931183 21667892444 8839528376 77671688743 31024367232 89840380380 4873771465 14736820809 142327968181 115923386349 32203682223 9608934637 87739160313 21...
result:
ok
Test #36:
score: 7
Accepted
time: 44ms
memory: 23328kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 12 10 16 18 19 20 21 22 23 24 25 25 23 28 29 29 31 32 31 32 35 36 37 37 38 40 41 41 35 44 22 46 21 48 49 50 51 23 48 50 32 56 57 58 58 60 61 32 63 9 65 46 62 68 12 42 71 72 73 40 75 63 77 14 79 79 81 82 82 82 82 30 76 88 89 9...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 5521438976 15261272599 10728067067 3645164128 23856372857 446697418 929867368 12088150858 30035383256 7293473665 4359793115 40865552617 55353413089 7616895721 34148444820 2529872987 53772209472 39426040232 3895610150 712023248 5474833320 2807877401 21416591895 366...
result:
ok
Test #37:
score: 7
Accepted
time: 48ms
memory: 23528kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 1 2 4 5 6 7 8 9 8 7 11 13 14 14 16 17 17 18 20 14 19 23 24 24 26 27 26 29 30 31 29 25 34 34 35 37 32 39 40 41 42 43 42 43 45 46 48 48 49 51 51 51 43 55 55 57 58 58 44 55 39 60 64 64 44 67 68 69 68 71 72 19 74 27 9 77 78 79 80 80 82 83 84 85 86 85 86 89 90 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 38153302526 130097547239 52388680982 69184293541 80459218361 14724080527 866710368 18319226622 80908501410 23324019935 32743579203 16938672359 5934264863 52906244180 23716977699 45587337949 14483777583 2954757299 19498267405 24049176238 9117766559 5805218194 21070...
result:
ok
Test #38:
score: 7
Accepted
time: 46ms
memory: 26004kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 5 6 0 8 8 10 11 12 9 14 15 16 17 18 19 20 21 7 23 24 25 26 27 28 29 30 31 32 33 34 35 22 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...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 307705295 740817932 103016 93590629 636968552 4207234 494349851 813091070 510525363 215228314 109359791 1042526314 759568979 271550316 293772874 1144161018 4572297 637369864 459711939 148096492 103770009 853464064 22376976 676525710 84286852 399680890 775723872 12...
result:
ok
Test #39:
score: 7
Accepted
time: 43ms
memory: 22456kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 2 3 4 2 4 7 8 8 10 10 12 13 14 15 16 17 15 16 20 21 22 21 24 18 26 13 28 19 30 14 32 33 34 35 35 37 33 39 40 41 41 26 32 45 46 47 30 49 50 31 52 52 18 55 55 36 48 48 19 49 62 62 31 65 11 67 68 68 9 71 72 73 74 75 76 77 78 78 76 81 82 82 71 36 39 87 88 87 9...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 17606249861 36754536423 31398535922 126896299427 75536620971 124572494315 61770969257 36419022307 25719602834 21613762047 19587768771 90018339815 32518184788 37664052696 132681842175 33458876552 10232954134 55087303729 27438862203 44821277009 63256973538 470954133...
result:
ok
Test #40:
score: 7
Accepted
time: 32ms
memory: 19944kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 96203127179 56234228902 33659229298 20054091922 292186192729 55908093901 136507199146 37505723434 132422932602 44038197362 134790779646 279535770445 79001683916 226259989838 4703942916 48668597404 166838756150 7495535255 287482795199 38180299940 258644451531 31204...
result:
ok
Subtask #5:
score: 0
Wrong Answer
Dependency #4:
100%
Accepted
Test #41:
score: 0
Wrong Answer
time: 47ms
memory: 21164kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 1 1 1 5 5 5 8 8 10 1 10 13 13 13 16 16 18 19 20 21 21 22 24 21 22 21 21 22 20 19 18 21 19 24 36 36 38 38 40 41 40 41 44 45 45 45 44 45 50 50 50 51 54 55 55 54 44 50 55 61 62 16 38 19 45 40 54 18 8 54 62 73 73 75 76 76 76 79 80 80 75 80 75 80 80 87 87 87 90...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 623921479551 431543310425 1501332694070 990170132425 126013474865 285582853373 251664690334 3151659572 246988608344 1083003931675 415110878987 1578414644343 1037654364244 333730794248 621265409233 91630070552 11048835306 223176372765 148123703322 55137304392 28199...
result:
wrong answer 3rd lines differ - on the 1st token, expected: '37308016868', found: '623921479551'
Subtask #6:
score: 0
Wrong Answer
Test #47:
score: 22
Accepted
time: 32ms
memory: 22716kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 0 1 4 5 5 7 7 9 9 11 12 13 13 11 14 12 14 19 20 19 20 23 24 25 26 26 28 28 30 31 32 33 33 35 35 30 32 31 37 41 42 43 24 44 46 46 48 49 50 51 51 53 54 55 55 56 56 48 50 54 44 59 49 25 59 67 68 67 68 71 71 72 72 75 76 76 78 79 80 37 80 83 83 85 86 85 79 41 8...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 44399242169 44212387526 45790536474 45755320631 44179830668 44674975190 45108846673 44925057561 45397405182 44060687307 44371967364 44521941379 44063691285 45721392614 44864217118 45409864033 44277589684 45749035882 45188069715 46494572380 45158343139 45090918080 ...
result:
ok
Test #48:
score: 0
Wrong Answer
time: 57ms
memory: 21568kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 1 0 1 5 5 5 8 9 9 11 11 11 14 14 16 17 18 19 20 19 20 20 20 19 20 27 28 28 27 27 16 29 34 34 17 1 9 5 34 41 18 1 1 16 41 47 47 47 50 51 52 50 51 29 20 52 58 58 58 58 58 59 64 64 64 64 66 69 69 69 71 69 69 71 69 73 78 78 78 81 82 83 82 83 86 87 88 86 88 86 ...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 116929011799 64943726054 64943726054 64943916158 246938261804 64944092623 64943726054 83843309686 150330269287 97132255114 73775482190 64943726054 64943726054 64943726054 64943726054 64943726054 64944034362 64943726054 218012158717 100751568878 64943726054 6494372...
result:
wrong answer 3rd lines differ - on the 1st token, expected: '64951344210', found: '116929011799'
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%