北理珠OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#13482 #95. 「2024 广东省赛」DFS 序 Accepted 100 3615 ms 8704 K C++ 17 / 656 B 1021 2024-06-01 10:01:45
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
int n;
int sz[200010];
long long ans[200010], w[200010];
vector<int> g[200010];
bool cmp(int x, int y) { return (long long)w[x] * sz[y] < (long long)w[y] * sz[x]; }
void dfs(int x) {
    for (int i = 0; i < g[x].size(); i++) {
        dfs(g[x][i]);
    }
    sort(g[x].begin(), g[x].end(), cmp);
    ans[x] = w[x], sz[x] = 1;
    for (int i = 0; i < g[x].size(); i++) {
        ans[x] += sz[x] * w[g[x][i]] + ans[g[x][i]];
        sz[x] += sz[g[x][i]];
        w[x] += w[g[x][i]];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        g[x].push_back(i);
    }
    dfs(1);
    cout << ans[1];
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：127 ms
内存：8672 KiB

输入文件（1.in） 

200000
7646 13490 57330089 2 93193 39868 155006 979242 609 4004056 1168756 1 7600415 10638 260015 97
<2220584 bytes omitted>

答案文件（1.ans） 

52918530899597711

用户输出 

52918530899597711

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：164 ms
内存：8640 KiB

输入文件（2.in） 

200000
2 1559377 24741019 12689 63659 66223105 1844640 62 8 59 909 4098 8262 103 312 26116360 587 44
<2217754 bytes omitted>

答案文件（2.ans） 

52173526807589704

用户输出 

52173526807589704

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：139 ms
内存：8704 KiB

输入文件（3.in） 

200000
77 32735260 132702 1286 346 2 1 365209 234904 2775 40 23 234 477 10924067 195160 604 186 1263
<2220174 bytes omitted>

答案文件（3.ans） 

53092505437322655

用户输出 

53092505437322655

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：174 ms
内存：8704 KiB

输入文件（4.in） 

200000
102 973 23297 8925 64205 16 3 10740477 5933474 37 4 10 14 34882912 1747049 12490 53 414 1234 
<2219794 bytes omitted>

答案文件（4.ans） 

52698927680410333

用户输出 

52698927680410333

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：172 ms
内存：8636 KiB

输入文件（5.in） 

200000
134858 10683131 250 44796 5 2387274 1839 447 925 239 487 76 43486 5311 294871 999 1160286 440
<2221570 bytes omitted>

答案文件（5.ans） 

52252835433664340

用户输出 

52252835433664340

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：171 ms
内存：8576 KiB

输入文件（6.in） 

200000
121 12 64927433 18 103546 16 11079605 100 2919 1429 1 5733243 4 16 436192 3602 652 3 4 102470
<2218363 bytes omitted>

答案文件（6.ans） 

52560721318709985

用户输出 

52560721318709985

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：117 ms
内存：8576 KiB

输入文件（7.in） 

200000
8 17028 224513 41 55661 6318190 226591 1792373 30 22438 19061 1972474 451294 96874 1657612 1 
<2220097 bytes omitted>

答案文件（7.ans） 

52564229876039943

用户输出 

52564229876039943

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：75 ms
内存：7860 KiB

输入文件（8.in） 

200000
2243 388 55143369 66929 2 3246944 15296 82492 127 124 126 72964 6132565 87534 1807786 4074 19
<2216650 bytes omitted>

答案文件（8.ans） 

79932293966678811

用户输出 

79932293966678811

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：65 ms
内存：7936 KiB

输入文件（9.in） 

200000
13239 600836 1 29 7496 98 36 100638 4066537 112 122 25051 41 446791 708593 5891 4749097 14256
<2212784 bytes omitted>

答案文件（9.ans） 

79940439494996369

用户输出 

79940439494996369

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：77 ms
内存：8064 KiB

输入文件（10.in） 

200000
2 1 1577 851650 13 9494 8 2384 3912 950 15 464 58783 4 2 4 3 643507 6777747 168000 11440 640 
<2214480 bytes omitted>

答案文件（10.ans） 

78318211574370074

用户输出 

78318211574370074

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：78 ms
内存：7936 KiB

输入文件（11.in） 

200000
8023083 2 1487454 202346 29088 1 13249085 2 2 6 7 4357 3520020 830045 2 4 21001844 1430 1 113
<2213891 bytes omitted>

答案文件（11.ans） 

78725730350901803

用户输出 

78725730350901803

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：74 ms
内存：7936 KiB

输入文件（12.in） 

200000
28639264 2012 5787 1782455 29 5 13 236993 215656 113283 24326 137 358 2116 116973 2 96 97 11 
<2213975 bytes omitted>

答案文件（12.ans） 

79335948950937471

用户输出 

79335948950937471

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：102 ms
内存：7936 KiB

输入文件（13.in） 

200000
34021 21896653 1 774 32 450 124 31133505 52 11516 26059 1150945 152 13 2 1522 2 5 55 593871 5
<2216415 bytes omitted>

答案文件（13.ans） 

79783109333160784

用户输出 

79783109333160784

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：71 ms
内存：7908 KiB

输入文件（14.in） 

200000
9783308 13 1087 2 3059 31486 3082800 76198 1 61 928331 26 2184507 3602 2 55043700 245394 2504
<2212730 bytes omitted>

答案文件（14.ans） 

79039159182809589

用户输出 

79039159182809589

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：72 ms
内存：7924 KiB

输入文件（15.in） 

200000
90112359 66441983 58814979 80267269 88074108 62755027 80192158 41138547 80711094 78287557 529
<2955380 bytes omitted>

答案文件（15.ans） 

1109888954959554638

用户输出 

1109888954959554638

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：80 ms
内存：7936 KiB

输入文件（16.in） 

200000
50406187 70030908 52166043 14239972 27710685 13444404 55032004 2099321 27134069 77560754 9283
<2955989 bytes omitted>

答案文件（16.ans） 

1108027394481323327

用户输出 

1108027394481323327

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：67 ms
内存：7936 KiB

输入文件（17.in） 

200000
41331591 33455297 57363574 67285499 55431569 22174076 99565501 8365029 24999460 17789202 1460
<2955846 bytes omitted>

答案文件（17.ans） 

1110638011164822353

用户输出 

1110638011164822353

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：77 ms
内存：7880 KiB

输入文件（18.in） 

200000
857137 43418112 88546915 80343387 85228166 60764751 47157021 61234683 95971170 5197145 775987
<2955010 bytes omitted>

答案文件（18.ans） 

1107752061446736178

用户输出 

1107752061446736178

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：81 ms
内存：7936 KiB

输入文件（19.in） 

200000
66484442 18738672 71838913 8781700 29672472 24875176 53799806 34354017 75466758 14919980 5882
<2955868 bytes omitted>

答案文件（19.ans） 

1110538207992640683

用户输出 

1110538207992640683

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：86 ms
内存：7960 KiB

输入文件（20.in） 

200000
69147100 57186366 19889515 62173962 31224619 96056298 42036899 30359124 99703946 78565640 286
<2955732 bytes omitted>

答案文件（20.ans） 

1109333218313670516

用户输出 

1109333218313670516

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：67 ms
内存：7872 KiB

输入文件（21.in） 

200000
16476699 88101158 45797440 9371110 83727501 42293478 88073676 95051155 91681920 30463321 4309
<2955262 bytes omitted>

答案文件（21.ans） 

1109905068983909623

用户输出 

1109905068983909623

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：93 ms
内存：8536 KiB

输入文件（22.in） 

200000
22465019 17157102 5997854 36051214 41344422 17506720 3245061 98893574 93699808 58539199 24297
<2961289 bytes omitted>

答案文件（22.ans） 

1003468055537636686

用户输出 

1003468055537636686

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：169 ms
内存：8576 KiB

输入文件（23.in） 

200000
59380358 7990199 54388753 43315031 83026586 35786253 15117679 85095891 64183597 26145892 7180
<2960885 bytes omitted>

答案文件（23.ans） 

1001133055956043053

用户输出 

1001133055956043053

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：157 ms
内存：8576 KiB

输入文件（24.in） 

200000
13879525 88872422 86426843 81981244 35745782 8252237 88879870 32336681 17259247 9799053 54116
<2961196 bytes omitted>

答案文件（24.ans） 

1006539070408400084

用户输出 

1006539070408400084

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：127 ms
内存：8576 KiB

输入文件（25.in） 

200000
42027955 97422009 1180650 36539900 52794685 80220051 39247640 72772081 76999239 41140209 2508
<2961358 bytes omitted>

答案文件（25.ans） 

1001987361853370327

用户输出 

1001987361853370327

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：161 ms
内存：8704 KiB

输入文件（26.in） 

200000
49951497 67023460 43575553 99249673 25509432 24728803 25175166 18161697 11740710 17855302 105
<2960915 bytes omitted>

答案文件（26.ans） 

1004485887208840390

用户输出 

1004485887208840390

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：165 ms
内存：8704 KiB

输入文件（27.in） 

200000
25954683 38033439 16408582 9872693 74886488 59337429 26798573 68183895 49288259 86280807 7415
<2961343 bytes omitted>

答案文件（27.ans） 

1006608001537197997

用户输出 

1006608001537197997

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：82 ms
内存：7488 KiB

输入文件（28.in） 

200000
23748479 4399160 57739347 97369535 94167471 16161141 67979009 65646291 64101965 11880888 1176
<2177738 bytes omitted>

答案文件（28.ans） 

1331728490141167476

用户输出 

1331728490141167476

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：78 ms
内存：7556 KiB

输入文件（29.in） 

200000
54628345 71862006 21293914 28595692 72709009 22535843 83349083 65747313 29248155 60528710 143
<2677553 bytes omitted>

答案文件（29.ans） 

1291929915888720245

用户输出 

1291929915888720245

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：82 ms
内存：7692 KiB

输入文件（30.in） 

200000
4 26920126 758805 55 4 20 10 589946 9 226435 5 5941612 9493 1436951 189643 3 129069 3560 801 
<2320563 bytes omitted>

答案文件（30.ans） 

56067769931199422

用户输出 

56067769931199422

系统信息 

Exited with return code 0
测试点 #31
Accepted
得分：100
用时：79 ms
内存：7732 KiB

输入文件（31.in） 

200000
7 44392 2 317126 7506104 411079 707 1678 22 2456477 193 982535 1973148 282 189596 332001 3 12
<2322106 bytes omitted>

答案文件（31.ans） 

56018780726759944

用户输出 

56018780726759944

系统信息 

Exited with return code 0
测试点 #32
Accepted
得分：100
用时：68 ms
内存：7680 KiB

输入文件（32.in） 

200000
333840 872 9804985 27705 4 8482715 54 1950 1 97947 4732162 1686 5734 11835 933 3666 218 9 295
<2320743 bytes omitted>

答案文件（32.ans） 

56636310850921290

用户输出 

56636310850921290

系统信息 

Exited with return code 0
测试点 #33
Accepted
得分：100
用时：63 ms
内存：7680 KiB

输入文件（33.in） 

200000
834085 622626 214 2 3 2021175 4418568 9 201864 240575 110660 19 1243021 3530 1 13 2 5035 8842
<2320968 bytes omitted>

答案文件（33.ans） 

56739754417744062

用户输出 

56739754417744062

系统信息 

Exited with return code 0
测试点 #34
Accepted
得分：100
用时：76 ms
内存：7680 KiB

输入文件（34.in） 

200000
227157 1 31 173706 1186 485156 15 612 3567896 1 54254 1530 4188075 46 5876 8 1 196 1010564 24
<2321180 bytes omitted>

答案文件（34.ans） 

55722757560718780

用户输出 

55722757560718780

系统信息 

Exited with return code 0
测试点 #35
Accepted
得分：100
用时：79 ms
内存：7672 KiB

输入文件（35.in） 

200000
18 10501820 14 3854257 27 1 608998 3439296 104296 375 31 1 1680 4096107 22933952 10125754 669
<2320964 bytes omitted>

答案文件（35.ans） 

55276855939084899

用户输出 

55276855939084899

系统信息 

Exited with return code 0
北理珠OJ Powered by SYZOJ.