QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#323139 | #952. Spring cleaning | Camillus | 0 | 274ms | 13028kb | C++20 | 4.1kb | 2024-02-08 18:11:30 | 2024-02-08 18:11:32 |
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 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);
if (u == 0) {
break;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Accepted
time: 1ms
memory: 4588kb
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
Wrong Answer
time: 187ms
memory: 6436kb
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:
89011 33577908 23454 23216 23454 23461 23476 23449 23470 23458 23474 23466 23465 23470 67132587 23462 23462 23471 23466 33577907 23460 23452 23468 23964 23462 23458 23456 23458 23470 23457 83909290 33577384 16800678 23461 33578409 23976 23455 23459 23458 23462 16800689 23460 23455 23462 23471 169972...
result:
wrong answer 1st lines differ - expected: '23481', found: '89011'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 11ms
memory: 4996kb
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:
168581433
result:
wrong answer 1st lines differ - expected: '84526', found: '168581433'
Subtask #3:
score: 0
Time Limit Exceeded
Test #8:
score: 0
Time Limit Exceeded
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
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
Wrong Answer
Test #19:
score: 19
Accepted
time: 209ms
memory: 10096kb
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:
-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:
ok 65535 lines
Test #20:
score: -19
Wrong Answer
time: 274ms
memory: 10384kb
input:
65535 4945 42941 23543 45541 34209 47644 12262 63786 38185 22551 3126 54952 11257 17620 53826 57165 30291 59502 23927 492 5929 64283 64528 57715 29045 63287 26916 59711 10374 25832 3012 35364 52502 43385 51892 37943 19200 33799 9796 56123 63643 35588 2879 38798 22405 12420 21846 39766 20399 51516 62...
output:
98263 98304 98745 98279 98292 33653207 98788 99025 98274 98289 98267 98771 98277 98250 98290 98298 98256 98268 99015 98271 98273 98750 229352 229852 229331 67207874 98301 98290 98281 98296 98777 33652969 33652930 67273436 33652937 33652974 67273183 33652959 33652960 98267 164295 98274 98291 98289 98...
result:
wrong answer 1st lines differ - expected: '98244', found: '98263'
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 252ms
memory: 13028kb
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:
117138 -1 -1 117137 -1 -1 117137 -1 117143 117143 -1 117140 117136 117141 117139 117140 117142 117145 117141 117146 -1 -1 -1 -1 -1 117138 -1 -1 117136 117139 -1 117144 117141 -1 117138 117144 117139 117141 117140 117137 117137 117141 117138 117137 -1 117144 117139 -1 117139 117146 -1 117140 -1 -1 -1...
result:
wrong answer 7th lines differ - expected: '117136', found: '117137'
Subtask #7:
score: 0
Skipped
Dependency #1:
0%