QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731361 | #5580. Branch Manager | beamishboys# | AC ✓ | 130ms | 21312kb | C++23 | 664b | 2024-11-10 02:34:51 | 2024-11-10 02:34:52 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mn = 2e5+5;
int in[mn], out[mn];
vector<int> adj[mn];
int dfs(int cur, int t = 0) {
in[cur] = t;
for (int a : adj[cur]) t = dfs(a, t);
out[cur] = t;
return out[cur]+1;
}
int main() {
int n, m; cin >> n >> m;
for (int i =0; i < n-1; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
}
for (int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end());
dfs(1);
int time = 0;
int i = 0;
for (; i < m; i++) {
int d; cin >> d;
if (out[d] >= time) {
time = max(in[d], time);
}
else break;
}
cout << i << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
8 5 1 2 4 8 4 6 1 4 2 5 4 7 2 3 5 2 6 4 8
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
4 4 1 2 1 3 1 4 3 2 3 4
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5592kb
input:
2 2 1 2 2 2
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 82ms
memory: 13804kb
input:
200000 200000 161672 172858 146306 146322 61159 61510 140802 145171 194221 195447 73888 80278 77016 77115 1382 1417 186221 195091 78442 78451 171750 172141 147707 151432 182664 182798 143183 147414 156646 162546 6630 6706 18452 18519 99764 99811 153419 153707 125659 129068 179317 185954 13947 14278 ...
output:
3563
result:
ok single line: '3563'
Test #5:
score: 0
Accepted
time: 130ms
memory: 13808kb
input:
200000 200000 73559 73695 138868 139314 169919 172147 3308 3348 35604 35605 180658 181072 114345 115218 146174 146449 21102 21786 107951 109513 9726 9970 50 51 154991 159020 49941 50155 4670 4671 90651 90653 76212 81669 173486 173539 143322 143389 191619 193955 14951 15097 136371 141417 59383 60502 ...
output:
200000
result:
ok single line: '200000'
Test #6:
score: 0
Accepted
time: 12ms
memory: 6548kb
input:
20000 20000 2163 2201 12429 12586 3232 3520 15314 15325 802 804 4746 5448 1061 1088 13374 13407 13566 14044 19080 19290 16461 16914 11323 11324 1594 1595 3588 3980 17217 19232 1828 1941 10180 10195 3112 4898 12823 13622 16020 16093 2773 2892 12885 13851 18980 19043 10476 10493 9902 10012 15286 15440...
output:
20000
result:
ok single line: '20000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
34 392 1 25 1 9 1 21 2 27 1 7 1 20 2 11 6 28 3 33 1 22 1 8 1 10 1 5 1 23 1 14 3 30 2 6 1 12 1 15 1 19 1 18 1 31 1 2 1 16 2 26 1 3 1 4 5 24 10 32 3 34 1 13 2 17 1 29 6 6 28 28 28 28 28 28 2 11 11 28 28 28 28 28 28 28 28 28 2 11 11 11 11 11 11 11 11 11 11 11 11 11 11 2 17 17 17 17 17 17 17 17 17 17 17...
output:
11
result:
ok single line: '11'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5544kb
input:
3 5 1 2 2 3 2 3 2 2 3
output:
5
result:
ok single line: '5'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
198 188 129 142 82 83 31 32 93 98 5 6 86 87 71 75 78 79 98 102 57 66 45 52 90 91 142 179 151 158 172 183 15 18 189 194 159 168 148 153 18 21 86 141 166 195 2 4 38 41 111 112 87 127 13 15 88 94 133 174 105 106 3 5 87 97 73 80 121 129 23 25 43 70 127 166 129 143 56 65 39 42 56 61 174 177 2 3 37 54 70 ...
output:
188
result:
ok single line: '188'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
200 187 88 89 137 138 58 59 19 20 99 100 127 128 48 49 173 174 17 18 75 76 136 137 128 129 100 101 97 98 51 52 4 5 73 74 6 7 138 139 187 188 151 152 37 38 43 44 23 24 120 121 196 197 98 99 42 43 109 110 89 90 130 131 125 126 62 63 106 107 78 79 190 191 93 94 168 169 161 162 158 159 36 37 61 62 165 1...
output:
187
result:
ok single line: '187'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5648kb
input:
8 8 4 7 2 4 2 6 2 3 1 8 1 2 4 5 7 8 6 4 7 7 4 4
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 99ms
memory: 5716kb
input:
200000 200000 1 99604 1 92192 1 76766 1 86883 1 77992 1 107401 1 63372 1 162116 1 120232 1 37089 1 93172 1 34383 1 196526 1 25633 1 177265 1 159035 1 149616 1 17433 1 39492 1 671 1 24966 1 55858 1 85586 1 28298 1 4970 1 172349 1 139382 1 121034 1 131345 1 184645 1 68952 1 29195 1 129941 1 83951 1 17...
output:
200000
result:
ok single line: '200000'
Test #13:
score: 0
Accepted
time: 70ms
memory: 5572kb
input:
200000 200000 1 79738 1 45523 1 56820 1 102764 1 147970 1 111851 1 1365 1 63366 1 29471 1 147031 1 169622 1 176480 1 111848 1 43158 1 98829 1 112119 1 159407 1 102889 1 162277 1 141904 1 1832 1 105887 1 164798 1 51504 1 72907 1 159194 1 23839 1 165104 1 178506 1 54064 1 199386 1 137629 1 137660 1 41...
output:
31596
result:
ok single line: '31596'
Test #14:
score: 0
Accepted
time: 125ms
memory: 21312kb
input:
200000 200000 28491 28492 608 609 175084 175085 63627 63628 42437 42438 34167 34168 94439 94440 65456 65457 12245 12246 78262 78263 39341 39342 168132 168133 21429 21430 42212 42213 84000 84001 25125 25126 104132 104133 129301 129302 48878 48879 107778 107779 192433 192434 105565 105566 40250 40251 ...
output:
200000
result:
ok single line: '200000'
Test #15:
score: 0
Accepted
time: 124ms
memory: 21292kb
input:
200000 200000 168459 168460 15232 15233 192243 192244 130078 130079 65195 65196 37807 37808 109352 109353 17134 17135 20465 20466 28749 28750 141730 141731 97789 97790 154131 154132 175321 175322 7161 7162 106516 106517 62592 62593 95590 95591 65225 65226 112792 112793 113385 113386 90609 90610 2361...
output:
200000
result:
ok single line: '200000'
Test #16:
score: 0
Accepted
time: 117ms
memory: 13320kb
input:
200000 200000 62244 123458 39383 154122 46805 142116 71577 71578 6372 6373 68089 68090 31520 31521 13912 13913 22548 22549 4640 198274 64215 64216 88180 88181 37934 166771 71921 71922 17032 17033 76272 76273 47840 133692 1343 1344 16085 16086 77340 77341 88700 103980 71529 71530 62541 62542 35671 35...
output:
200000
result:
ok single line: '200000'
Test #17:
score: 0
Accepted
time: 100ms
memory: 13232kb
input:
200000 200000 62242 62243 44272 108109 49004 49005 14401 14402 63306 63307 89216 104665 19599 156425 54608 54609 46437 46438 55382 142176 8754 8755 10855 187941 36963 36964 68678 68679 1981 1982 66883 66884 76331 187997 32781 128583 61109 61110 78094 78095 53074 188371 40251 40252 32361 178425 31685...
output:
140902
result:
ok single line: '140902'
Test #18:
score: 0
Accepted
time: 101ms
memory: 6728kb
input:
200000 200000 3516 104976 1569 142576 646 36086 3818 44813 3303 43028 1202 156768 3697 67333 1739 174091 353 81325 3194 114577 1324 117981 1675 13872 3562 86276 733 37365 836 81804 2736 33189 2965 179808 2832 106765 1204 111744 1554 164782 1082 83661 125 84986 1309 68817 634 168972 2341 151930 1410 ...
output:
200000
result:
ok single line: '200000'
Test #19:
score: 0
Accepted
time: 91ms
memory: 7144kb
input:
200000 200000 1236 1237 5736 55984 3403 155825 3637 122025 8960 133788 7369 150928 3073 3074 6412 157336 5158 144490 5034 108204 3478 3479 8796 52783 8678 184693 812 169399 5456 169518 3556 31452 1507 74151 6634 17726 1901 188183 7633 25752 9094 146439 1732 161061 392 34261 2727 15276 9270 89725 826...
output:
143317
result:
ok single line: '143317'