QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323169 | #952. Spring cleaning | Camillus | 0 | 0ms | 3532kb | C++20 | 4.0kb | 2024-02-08 18:59:40 | 2024-02-08 18:59:41 |
Judging History
answer
/// @author Camillus
#include <bits/stdc++.h>
using namespace std;
static constexpr int maxn = 8;
vector<int> g[maxn];
int p[maxn];
int sz[maxn];
int cnt[maxn];
int root = 0;
void dfs1(int u) {
sz[u] = 1;
auto it = find(g[u].begin(), g[u].end(), p[u]);
if (it != g[u].end()) g[u].erase(it);
if (g[u].empty()) {
cnt[u] = 1;
return;
}
for (int v : g[u]) {
p[v] = u;
dfs1(v);
sz[u] += sz[v];
cnt[u] += cnt[v];
}
int &f = g[u].front();
for (int &v : g[u]) {
if (sz[v] > sz[f]) {
swap(f, v);
}
}
}
int tin[maxn];
int head[maxn];
int timer = 0;
void dfs2(int u) {
tin[u] = timer++;
if (head[u] == 0) {
head[u] = u;
}
if (!g[u].empty()) {
head[g[u].front()] = head[u];
}
for (int v : g[u]) {
dfs2(v);
}
}
namespace st {
using value_t = array<int, 2>;
value_t cnt[maxn * 2 - 1];
bool reversed[maxn * 2 - 1];
constexpr value_t merge(const value_t &first, const value_t &second) {
return {first[0] + second[0], first[1] + second[1]};
}
inline void apply(int x) {
swap(cnt[x][0], cnt[x][1]);
reversed[x] ^= 1;
}
inline void push(int x) {
if (reversed[x]) {
apply(x * 2 + 1);
apply(x * 2 + 2);
reversed[x] = false;
}
}
void reverse(int l, int r, int x = 0, int lx = 0, int rx = maxn) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
apply(x);
return;
}
push(x);
reverse(l, r, x * 2 + 1, lx, (lx + rx) / 2);
reverse(l, r, x * 2 + 2, (lx + rx) / 2, rx);
cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
}
value_t get(int i, int x = 0, int lx = 0, int rx = maxn) {
if (rx - lx == 1) {
return cnt[x];
}
push(x);
if (i < (lx + rx) / 2) {
return get(i, x * 2 + 1, lx, (lx + rx) / 2);
} else {
return get(i, x * 2 + 2, (lx + rx) / 2, rx);
}
}
void build(int n) {
for (int u = 1; u <= n; u++) {
int x = maxn + tin[u] - 1;
cnt[x][::cnt[u] % 2] = 1;
}
for (int x = maxn - 2; x >= 0; x--) {
cnt[x] = merge(cnt[x * 2 + 1], cnt[x * 2 + 2]);
}
}
} // namespace st
void reverse_path(int u) {
while (true) {
int v = head[u];
st::reverse(tin[v], tin[u] + 1);
u = v;
if (u == root) {
break;
} else {
u = p[u];
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int u = 1; u <= n; u++) {
if (g[u].size() > 1) {
root = u;
}
}
dfs1(root);
dfs2(root);
st::build(n);
while (q--) {
int d;
cin >> d;
map<int, int> c;
for (int i = 0; i < d; i++) {
int u;
cin >> u;
c[u] ^= 1;
}
for (auto &[u, k] : c) {
if (g[u].size() == 0) {
k ^= 1;
}
}
for (auto &[u, k] : c) {
if (k) {
reverse_path(u);
}
}
auto result = st::cnt[0];
result[1] += d;
if (st::get(0)[1]) {
cout << -1 << '\n';
} else {
cout << (result[0] - 1) * 2 + result[1] << '\n';
}
for (auto &[u, k] : c) {
if (k) {
reverse_path(u);
}
}
}
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Accepted
time: 0ms
memory: 3532kb
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
Runtime Error
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: 0
Runtime Error
Test #3:
score: 0
Runtime Error
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:
result:
Subtask #3:
score: 0
Runtime Error
Test #8:
score: 0
Runtime Error
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:
result:
Subtask #4:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
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
Runtime Error
Test #19:
score: 0
Runtime Error
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
Runtime Error
Test #24:
score: 0
Runtime Error
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%