QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #69644 | #2999. 春节十二响 | Land_ER | 5 | 41ms | 18044kb | C++11 | 1.9kb | 2022-12-29 10:27:06 | 2022-12-29 10:27:07 |
Judging History
answer
#include <bits/stdc++.h>
#define i64 long long int
#define N 200005
void read(int *w) {
*w = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c))
*w = (*w) * 10 + c - '0', c = getchar();
return;
}
int n;
int m[N], f[N];
std::vector<int> graph[N];
int deg[N];
void init(void) {
read(&n);
for(int i = 1; i <= n; ++ i)
read(m + i);
for(int i = 2; i <= n; ++ i)
read(f + i), graph[f[i]].push_back(i), ++ deg[i], ++ deg[f[i]];
return;
}
namespace subtask1 {
int mx = 0, se = 0;
std::vector<int> val[2];
void dfs(int now, int *col, int type) {
col[now] = type;
for(int e : graph[now])
if(e != f[now])
dfs(e, col, type);
return;
}
void solve(void) {
if(deg[1] == 1) {
i64 ans = 0;
for(int i = 1; i <= n; ++ i)
ans += m[i];
printf("%lld\n", ans);
return;
}
int col[N];
for(int i = 2; i <= n; ++ i)
if(m[i] > m[mx])
mx = i;
dfs(graph[1].at(0), col, 0);
dfs(graph[1].at(1), col, 1);
i64 ans = 0x3f3f3f3f3f3f3f3fll;
for(int i = 2; i <= n; ++ i) {
if(i == mx)
continue;
if(col[i] == col[mx])
val[0].push_back(m[i]);
else
val[1].push_back(m[i]);
}
i64 sum0 = 0;
for(int e : val[1])
sum0 += e;
std::sort(val[0].begin(), val[0].end());
std::sort(val[1].begin(), val[1].end());
auto ptr0 = val[0].begin(), ptr1 = val[1].begin();
while(ptr0 != val[0].end()) {
while(ptr1 != val[1].end()) {
if(*ptr1 <= *ptr0)
sum0 -= *ptr1, ++ ptr1;
else
break;
}
ans = std::min(sum0 + *ptr0, ans);
++ ptr0;
}
printf("%lld\n", ans + m[mx] + m[1]);
return;
}
}
void solve(void) {
int flag = 0;
for(int i = 1; i <= n; ++ i) {
if(deg[i] > 2) {
flag = 1;
break;
}
}
if(!flag)
subtask1::solve();
return;
}
int main(void) {
init();
solve();
return 0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 1ms
memory: 8472kb
input:
3 4 10 5 1 2
output:
19
result:
ok single line: '19'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 8020kb
input:
5 10 8 1 1 7 1 1 2 2
output:
result:
wrong answer 1st lines differ - expected: '25', found: ''
Test #3:
score: 0
Wrong Answer
time: 5ms
memory: 8116kb
input:
10 1 2 2 1 1 2 1 1 1 2 1 1 1 2 5 5 5 8 1
output:
result:
wrong answer 1st lines differ - expected: '7', found: ''
Test #4:
score: 0
Wrong Answer
time: 5ms
memory: 8032kb
input:
10 1 1 2 1 2 2 1 2 1 1 1 2 3 4 3 6 2 1 6
output:
result:
wrong answer 1st lines differ - expected: '7', found: ''
Test #5:
score: 0
Wrong Answer
time: 6ms
memory: 8212kb
input:
15 5 9 5 1 7 3 8 3 1 7 3 1 1 5 8 1 2 2 2 4 1 5 1 2 9 7 12 1 12
output:
result:
wrong answer 1st lines differ - expected: '25', found: ''
Test #6:
score: 0
Wrong Answer
time: 4ms
memory: 8056kb
input:
16 8 9 19 9 13 9 17 8 9 20 20 7 2 12 19 6 1 2 1 4 3 5 5 8 6 10 3 8 7 4 3
output:
result:
wrong answer 1st lines differ - expected: '85', found: ''
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 8112kb
input:
16 177269241 136479857 518040716 590690929 837228149 71462256 887232525 317436776 138552464 727415824 697621256 859965262 588521417 821100487 594324041 92665222 1 2 1 1 2 2 3 3 5 8 3 8 5 3 5
output:
result:
wrong answer 1st lines differ - expected: '2339518886', found: ''
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 8056kb
input:
16 439163150 802894105 828281100 29854078 492638605 752259707 917086603 810075381 743328523 497018778 360212988 603293784 85540195 33829826 50134176 30721768 1 1 2 3 1 3 7 1 3 4 10 2 9 3 3
output:
result:
wrong answer 1st lines differ - expected: '2994606234', found: ''
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 8048kb
input:
16 95 84 71 72 11 77 100 97 72 93 90 77 1000 33 19 31 1 1 3 3 1 2 5 2 3 8 9 12 5 7 3
output:
result:
wrong answer 1st lines differ - expected: '1334', found: ''
Test #10:
score: 0
Wrong Answer
time: 14ms
memory: 14448kb
input:
100000 51 23 6 31 25 88 47 2 84 90 10 56 97 84 51 74 85 64 21 29 20 21 62 62 36 30 81 82 91 62 53 94 36 10 76 60 49 22 14 32 64 23 39 60 58 90 34 43 53 6 71 24 78 84 86 13 65 18 46 56 79 50 1 66 59 76 26 60 49 91 91 12 13 30 72 70 71 5 64 75 62 86 98 39 69 35 3 34 53 48 41 31 49 93 49 7 20 26 66 68 ...
output:
1151
result:
wrong answer 1st lines differ - expected: '2529557', found: '1151'
Test #11:
score: 0
Wrong Answer
time: 24ms
memory: 18044kb
input:
150000 1780 14021 14043 16222 20687 24893 42032 47007 49300 52496 55196 60042 61228 69764 76485 77097 79859 80602 89003 92297 99254 101745 110985 117001 123788 128038 128171 136063 138089 141214 144843 157181 163051 165982 169166 170552 175768 180315 184163 188339 190724 191813 192841 199155 204364 ...
output:
2999909267
result:
wrong answer 1st lines differ - expected: '35463479060852', found: '2999909267'
Test #12:
score: 0
Wrong Answer
time: 41ms
memory: 17824kb
input:
150000 797908089 784987073 46944837 930191726 921098399 310954288 142542503 183158851 498350060 133840827 989090507 980304605 709717903 683657094 583791273 318822313 942189883 219717636 361991649 141603401 9012971 822131679 188198712 434976006 71544379 947141339 106477492 141627901 988298100 4059125...
output:
5797655023
result:
wrong answer 1st lines differ - expected: '35453836287189', found: '5797655023'
Test #13:
score: 0
Wrong Answer
time: 5ms
memory: 8100kb
input:
2000 100 71 65 47 56 12 42 30 54 22 36 97 92 38 84 99 64 57 85 98 39 25 11 17 20 26 66 81 92 64 37 43 35 1 41 42 65 35 71 18 56 6 14 47 95 49 97 10 57 81 59 47 5 69 63 77 95 29 57 38 44 46 81 30 98 21 71 62 55 93 31 10 50 44 8 45 44 57 54 100 37 13 47 94 33 61 70 27 89 78 17 85 23 97 14 21 17 37 82 ...
output:
result:
wrong answer 1st lines differ - expected: '19842', found: ''
Test #14:
score: 0
Wrong Answer
time: 5ms
memory: 8088kb
input:
2000 1 3 5 5 7 8 9 10 11 11 12 12 12 12 12 13 13 13 14 14 15 16 16 16 17 17 18 21 22 22 23 23 23 25 25 25 26 26 27 28 28 28 28 28 28 29 29 29 30 31 31 32 32 33 33 35 36 36 37 37 37 38 39 39 39 40 41 41 41 41 42 42 42 42 43 43 44 45 45 46 46 47 48 48 49 49 50 50 51 51 52 52 52 52 53 53 53 53 54 54 55...
output:
result:
wrong answer 1st lines differ - expected: '198663', found: ''
Test #15:
score: 0
Wrong Answer
time: 2ms
memory: 8188kb
input:
2000 1 1 3 3 4 4 4 5 5 7 7 7 7 7 8 8 9 9 9 10 10 11 11 12 12 12 13 13 14 14 14 14 14 15 15 16 16 16 17 17 17 17 18 18 19 19 19 20 20 21 21 23 24 24 25 25 27 27 27 27 28 28 29 29 29 30 30 31 31 32 32 32 32 33 34 34 34 34 35 35 35 37 38 39 39 40 40 41 42 42 44 44 45 46 46 46 46 48 49 50 51 51 51 51 52...
output:
result:
wrong answer 1st lines differ - expected: '175767', found: ''
Test #16:
score: 0
Wrong Answer
time: 17ms
memory: 14524kb
input:
200000 753 856 722 833 51 114 999 177 365 374 755 761 420 327 354 357 834 691 665 533 926 768 823 753 332 726 832 11 103 774 30 855 982 751 39 32 216 389 561 580 114 315 693 533 993 46 242 178 88 906 710 13 673 884 118 357 610 949 367 712 723 397 918 704 499 308 87 715 696 647 294 161 313 338 693 30...
output:
result:
wrong answer 1st lines differ - expected: '18276228', found: ''
Test #17:
score: 0
Wrong Answer
time: 22ms
memory: 14532kb
input:
200000 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:
result:
wrong answer 1st lines differ - expected: '18171535', found: ''
Test #18:
score: 0
Wrong Answer
time: 19ms
memory: 14432kb
input:
199999 823285901 477166963 348450438 320236141 201658155 230106556 298811949 201089971 578905148 921146489 55355606 661735064 864805465 934691341 805255537 654582721 368495076 22691277 28126605 645131210 633602063 438131799 214756248 647514920 480491658 906960147 142206414 397775189 633189604 618961...
output:
result:
wrong answer 1st lines differ - expected: '17018327325681', found: ''
Test #19:
score: 0
Wrong Answer
time: 23ms
memory: 14588kb
input:
199998 787276771 914335740 739025048 444916565 545108873 429907832 521181033 625114241 123679075 635504340 432788154 751979906 270531673 870643710 528513199 630155900 983812400 610529578 918361469 61376025 915950583 491917202 6303438 639611089 695103305 30836351 854978506 863964151 713886031 6278892...
output:
result:
wrong answer 1st lines differ - expected: '17174054861956', found: ''
Test #20:
score: 0
Wrong Answer
time: 24ms
memory: 14444kb
input:
199997 541412948 31954496 577614307 653157996 354253149 377225109 594337307 128057389 106954411 85250057 953326084 107845778 518626668 969193653 882540733 305581838 730205341 84480784 267127777 383392198 8062772 547669300 824385066 911658679 550924598 468293145 447934189 599967513 103929466 18513528...
output:
result:
wrong answer 1st lines differ - expected: '17135092871559', found: ''