QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323147 | #952. Spring cleaning | Camillus | 18 | 29ms | 17624kb | C++20 | 1.8kb | 2024-02-08 18:22:52 | 2024-02-08 18:22:53 |
Judging History
answer
/// @author Camillus
#include <bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<pair<int, int>> edges(n - 1);
for (auto &[u, v] : edges) {
cin >> u >> v;
}
auto result = [&edges]() -> int {
int n = (int)edges.size() + 1;
vector<vector<int>> g(n);
for (auto [u, v] : edges) {
u--;
v--;
g[u].push_back(v);
g[v].push_back(u);
}
int answer = 0;
auto dfs = [&](auto &&self, int u, int p) -> int {
if (g[u].size() == 1) {
return 1;
}
int sum = 0;
for (int v : g[u]) {
if (v == p) {
continue;
}
int current = self(self, v, u);
if (current % 2 == 1) {
answer += 1;
} else {
answer += 2;
}
sum += current;
}
return sum;
};
int root = 0;
for (int u = 0; u < n; u++) {
if (g[u].size() > 1) {
root = u;
}
}
int current = dfs(dfs, root, -1);
if (current % 2 == 1) {
return -1;
} else {
return answer;
}
};
for (int i = 0; i < q; i++) {
edges.resize(n - 1);
int d;
cin >> d;
for (int u = 1; u <= d; u++) {
int v;
cin >> v;
edges.emplace_back(u + n, v);
}
cout << result() << '\n';
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
7 3 1 2 2 4 4 5 5 6 5 7 3 4 1 4 2 2 4 1 1
output:
-1 10 8
result:
ok 3 lines
Test #2:
score: -0
Time Limit Exceeded
input:
20000 5000 9844 2753 14120 15267 6630 9346 16091 21 11589 11672 7243 10729 9376 18990 19172 16424 15329 4466 19473 2205 9722 13188 13805 12632 9639 7877 10960 12697 1725 10231 13383 4059 9258 10586 18536 11667 5581 666 1382 7072 17656 11359 10793 10158 18150 13161 9758 4811 280 4330 3962 17592 10138...
output:
result:
Subtask #2:
score: 9
Accepted
Test #3:
score: 9
Accepted
time: 6ms
memory: 8768kb
input:
3000 1 1 592 1 797 1 1542 1 1567 1 2784 1 455 1 140 1 2242 1 910 1 1018 1 961 1 661 1 2408 1 1791 1 776 1 2894 1 369 1 435 1 2441 1 519 1 2223 1 102 1 1478 1 2261 1 1920 1 2541 1 1835 1 1918 1 848 1 25 1 1993 1 1020 1 2852 1 719 1 226 1 2 1 156 1 13 1 748 1 2521 1 1762 1 2164 1 2905 1 2949 1 2994 1 ...
output:
84526
result:
ok single line: '84526'
Test #4:
score: 0
Accepted
time: 10ms
memory: 8796kb
input:
3000 1 1 2019 1 111 1 1364 1 1771 1 2378 1 2159 1 573 1 207 1 2070 1 620 1 888 1 335 1 2837 1 1317 1 221 1 2000 1 2633 1 1302 1 644 1 472 1 1874 1 1882 1 1309 1 2781 1 2213 1 2904 1 1085 1 389 1 2838 1 91 1 1107 1 1086 1 1627 1 949 1 1394 1 883 1 2744 1 2385 1 2298 1 799 1 2313 1 315 1 498 1 2873 1 ...
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 10ms
memory: 10056kb
input:
100000 1 1 54145 1 79089 1 74333 1 80683 1 71589 1 36284 1 36065 1 23877 1 52252 1 79993 1 54257 1 38347 1 33461 1 80038 1 69156 1 67331 1 35581 1 91618 1 5993 1 38827 1 37059 1 50347 1 65914 1 64402 1 56981 1 32705 1 73315 1 11098 1 61719 1 12911 1 37000 1 57320 1 80865 1 39114 1 56767 1 62511 1 41...
output:
105104
result:
ok single line: '105104'
Test #6:
score: 0
Accepted
time: 18ms
memory: 13604kb
input:
70000 1 1 56319 1 32897 1 69246 1 59111 1 5845 1 44069 1 44563 1 19533 1 31995 1 22157 1 13502 1 1307 1 42537 1 60784 1 40363 1 31983 1 23071 1 11304 1 48416 1 57872 1 13827 1 29632 1 60886 1 12738 1 59496 1 29988 1 7876 1 15279 1 26569 1 62592 1 22819 1 8963 1 7119 1 61345 1 37243 1 449 1 28767 1 5...
output:
178192
result:
ok single line: '178192'
Test #7:
score: 0
Accepted
time: 26ms
memory: 15328kb
input:
100000 1 1 52670 1 51157 1 66285 1 71477 1 43626 1 30699 1 4723 1 27122 1 21210 1 4707 1 58285 1 25305 1 55346 1 61958 1 60032 1 11283 1 65277 1 91648 1 79039 1 6055 1 18033 1 56975 1 52220 1 24114 1 97939 1 64658 1 13743 1 19269 1 77333 1 66756 1 64395 1 34692 1 72311 1 58534 1 27471 1 35410 1 6411...
output:
207612
result:
ok single line: '207612'
Subtask #3:
score: 9
Accepted
Test #8:
score: 9
Accepted
time: 5ms
memory: 8976kb
input:
5000 1 1342 1343 4110 4111 1415 1416 2960 2961 504 505 2756 2757 4496 4497 4178 4179 1933 1934 661 662 2894 2895 4041 4042 286 287 4881 4882 2988 2989 281 282 3038 3039 782 783 3878 3879 4914 4915 4578 4579 3877 3878 1870 1871 3014 3015 411 412 2711 2712 1479 1480 4818 4819 1930 1931 733 734 290 291...
output:
87526
result:
ok single line: '87526'
Test #9:
score: 0
Accepted
time: 11ms
memory: 8936kb
input:
5000 1 4605 4606 4467 4468 236 237 804 805 44 45 3706 3707 3222 3223 1600 1601 3132 3133 3201 3202 83 84 4075 4076 2487 2488 4100 4101 2709 2710 1564 1565 730 731 3934 3935 2859 2860 3382 3383 1490 1491 2915 2916 2921 2922 4292 4293 2149 2150 4866 4867 3894 3895 1499 1500 4826 4827 1389 1390 2565 25...
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 14ms
memory: 12744kb
input:
99000 1 79771 79772 79219 79220 95025 95026 74528 74529 74958 74959 60316 60317 89522 89523 50423 50424 18943 18944 95708 95709 85436 85437 89245 89246 88864 88865 45298 45299 80243 80244 45568 45569 86109 86110 88381 88382 40781 40782 80453 80454 74733 74734 83094 83095 38257 38258 87260 87261 9654...
output:
150655
result:
ok single line: '150655'
Test #11:
score: 0
Accepted
time: 29ms
memory: 17624kb
input:
90000 1 82770 82771 86846 86847 57191 57192 2404 2405 72238 72239 38989 38990 4520 4521 85621 85622 38425 38426 88887 88888 84483 84484 84979 84980 55756 55757 81666 81667 84172 84173 84048 84049 86248 86249 35519 35520 34092 34093 26006 26007 37509 37510 46515 46516 50285 50286 28067 28068 82609 82...
output:
224806
result:
ok single line: '224806'
Test #12:
score: 0
Accepted
time: 21ms
memory: 11612kb
input:
90000 1 45387 45388 59683 59684 54643 54644 48430 48431 46674 46675 75808 75809 83944 83945 37142 37143 7492 7493 35485 35486 13045 13046 77367 77368 89390 89391 53121 53122 81728 81729 64058 64059 64306 64307 82272 82273 44564 44565 87969 87970 81932 81933 63077 63078 30731 30732 41593 41594 77746 ...
output:
131664
result:
ok single line: '131664'
Subtask #4:
score: 0
Time Limit Exceeded
Test #13:
score: 0
Time Limit Exceeded
input:
20000 300 2298 16922 18552 10941 5144 7836 2466 9076 15500 13240 2610 15368 46 12878 8306 1607 9979 8975 2496 19531 11248 4651 4852 18243 7396 1470 7610 10848 10295 14356 4459 5642 4890 16696 3731 3723 762 4227 13780 8107 13906 2311 9823 2028 15526 1892 6024 10011 9630 9756 9126 15139 14648 115 9097...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #19:
score: 0
Time Limit Exceeded
input:
65535 65535 1811 13118 468 385 23933 56882 4701 42452 49582 14109 22804 8146 20990 13165 2862 42235 19741 48554 50898 55957 62662 44085 48624 14885 7097 61368 19900 36151 553 50630 52087 31138 45875 33789 57834 46368 50259 10233 56656 29222 48661 58651 62042 50198 5077 28414 50381 15211 60800 37526 ...
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #24:
score: 0
Time Limit Exceeded
input:
100000 100000 48535 38306 85495 24582 10294 14137 41148 31842 32266 36977 2963 82055 78886 1396 81175 93259 80317 66239 83481 49641 35645 57424 97195 2160 53900 55968 4256 17352 95865 83196 64417 63683 64041 61292 3392 82881 22755 53454 71067 1268 2191 84847 66432 7544 15405 77351 50616 64123 97980 ...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%