Submission #658651

#TimeUsernameProblemLanguageResultExecution timeMemory
658651lunchbox1Spring cleaning (CEOI20_cleaning)C++17
28 / 100
1091 ms13036 KiB
/* Spring Cleaning https://oj.uz/problem/view/CEOI20_cleaning */ #include <bits/stdc++.h> using namespace std; const int N = 1e5; vector<int> g[N]; int p[N], c[N], z[N], o[N]; int dfs1(int i) { int s = 1, x = 0; c[i] = -1; for (int j : g[i]) if (p[i] != j) { p[j] = i; int t = dfs1(j); if (x > t) x = t, c[i] = j; s += t; } return s; } void dfs2(int r, int i) { static int t = 0; o[i] = t++; z[i] = r; if (c[i] != -1) dfs2(r, c[i]); for (int j : g[i]) if (p[i] != j && c[i] != j) dfs2(j, j); } int t0[N * 4], t1[N * 4], lz[N * 4]; void build(int k, int l, int r) { t0[k] = r - l + 1; if (l != r) { int m = (l + r) / 2; build(k << 1 | 0, l, m), build(k << 1 | 1, m + 1, r); } } void put(int k) { swap(t0[k], t1[k]); lz[k] ^= 1; } void update(int k, int l, int r, int ql, int qr) { if (ql > r || qr < l) return; else if (ql <= l && qr >= r) put(k); else { int m = (l + r) / 2; if (lz[k]) put(k << 1 | 0), put(k << 1 | 1), lz[k] = 0; update(k << 1 | 0, l, m, ql, qr), update(k << 1 | 1, m + 1, r, ql, qr); t0[k] = t0[k << 1 | 0] + t0[k << 1 | 1], t1[k] = t1[k << 1 | 0] + t1[k << 1 | 1]; } } int n; void update(int i) { while (i != -1) { update(1, 0, n - 1, o[z[i]], o[i]); i = p[z[i]]; } } int main() { ios::sync_with_stdio(0), cin.tie(0); int q; cin >> n >> q; for (int h = 0; h < n - 1; h++) { int i, j; cin >> i >> j, i--, j--; g[i].push_back(j), g[j].push_back(i); } int r = 0; while (g[r].size() == 1) r++; p[r] = -1; dfs1(r); dfs2(r, r); int l = 0; build(1, 0, n - 1); for (int i = 0; i < n; i++) if (g[i].size() == 1) update(i), l++; while (q--) { int d; cin >> d; vector<int> t(d), u; for (int& i : t) cin >> i, i--; sort(t.begin(), t.end()); int l_ = l + d; for (int i = 0, j; i < (int) t.size(); i = j) { j = i; while (j < (int) t.size() && t[i] == t[j]) j++; if ((g[t[i]].size() > 1) ^ ((j - i) % 2 == 0)) update(t[i]), u.push_back(t[i]); l_ -= g[t[i]].size() == 1; } cout << (l_ % 2 == 1 ? -1 : n + d + t0[1] - 2) << '\n'; for (int i : u) update(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...