QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#323163 | #952. Spring cleaning | Camillus | 0 | 131ms | 13316kb | C++20 | 4.2kb | 2024-02-08 18:45:43 | 2024-02-08 18:45:44 |
Judging History
answer
/// @author Camillus
#include <bits/stdc++.h>
using namespace std;
static constexpr int maxn = 1 << 17;
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];
constexpr value_t merge(const value_t &first, const value_t &second) {
value_t result = first;
result[0] += second[0];
result[1] += second[1];
return result;
}
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 + 1);
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 l, int r, int x = 0, int lx = 0, int rx = maxn) {
if (l >= rx || lx >= r) {
return value_t();
}
if (l <= lx && rx <= r) {
return cnt[x];
}
push(x);
return merge(
get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
);
}
void build(int n) {
for (int x = 0; x < maxn * 2 - 1; x++) {
cnt[x] = {0, 0};
reversed[x] = false;
}
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)[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
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5764kb
input:
7 3 1 2 2 4 4 5 5 6 5 7 3 4 1 4 2 2 4 1 1
output:
6 10 8
result:
wrong answer 1st lines differ - expected: '-1', found: '6'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 9ms
memory: 6172kb
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:
-1
result:
wrong answer 1st lines differ - expected: '84526', found: '-1'
Subtask #3:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 9ms
memory: 6720kb
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:
151082770
result:
wrong answer 1st lines differ - expected: '87526', found: '151082770'
Subtask #4:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 32ms
memory: 7792kb
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:
84173632 83912521 84043063 -1 -1 151545671 -1 134506555 -1 134507588 -1 -1 151220793 67333952 67202626 -1 251816774 218131783 117534020 -1 201549616 151283273 -1 -1 -1 -1 -1 134375483 -1 -1 -1 -1 268724552 167864899 84373056 84306763 84176202 117731395 -1 -1 -1 -1 -1 -1 100951370 201615417 134506819...
result:
wrong answer 1st lines differ - expected: '25404', found: '84173632'
Subtask #5:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 76ms
memory: 10608kb
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:
98286 98285 98287 98284 98284 98288 98286 98283 98283 98283 98283 98287 98289 98285 98285 98282 98282 98794 98282 98282 98282 98282 98282 98286 98286 98288 98290 98284 98284 98284 98284 98281 98281 98281 98281 98281 98793 98281 98281 98281 98281 98281 98281 98281 98281 98281 98281 98285 98285 98285 ...
result:
wrong answer 1st lines differ - expected: '-1', found: '98286'
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 131ms
memory: 13316kb
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:
-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 ...
result:
wrong answer 1st lines differ - expected: '117138', found: '-1'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%