Submission #1230308

#TimeUsernameProblemLanguageResultExecution timeMemory
1230308RakhimovAmirSpring cleaning (CEOI20_cleaning)C++20
100 / 100
138 ms17732 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using ll = long long; inline void debugMode() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE } const int N = 1e5 + 10; vector<int> v[N]; int n, q; int c[N], add[N], f[N], p[N], tin[N], tout[N], tt, st[N], sz[N], t[4 * N][2], upd[4 * N], rev[N], k; int res, root; void trace(int x, int p) { tin[x] = ++tt; int big = -1; for (auto to : v[x]) { if (to == p) { continue; } if (big == -1 || sz[to] > sz[big]) { big = to; } } // cout << x << " -> " << big << "\n"; if (big != -1) { st[big] = st[x]; trace(big, x); } for (auto to : v[x]) { if (to == p || to == big) { continue; } st[to] = to; trace(to, x); } tout[x] = tt; } void build(int x, int tl, int tr) { if (tl == tr) { t[x][0] = 1; return; } int tm = (tl + tr) / 2; build(2 * x, tl, tm); build(2 * x + 1, tm + 1, tr); t[x][0] = t[2 * x][0] + t[2 * x + 1][0]; } void push(int x) { if (upd[x] == 0) { return; } upd[2 * x] ^= 1; upd[2 * x + 1] ^= 1; upd[x] = 0; swap(t[2 * x][0], t[2 * x][1]); swap(t[2 * x + 1][0], t[2 * x + 1][1]); } void update(int x, int tl, int tr, int l, int r) { if (r < tl || l > tr) return; if (l <= tl && r >= tr) { upd[x] ^= 1; res -= t[x][1]; swap(t[x][0], t[x][1]); res += t[x][1]; return; } int tm = (tl + tr) / 2; push(x); update(2 * x, tl, tm, l, r); update(2 * x + 1, tm + 1, tr, l, r); t[x][0] = t[2 * x][0] + t[2 * x + 1][0]; t[x][1] = t[2 * x][1] + t[2 * x + 1][1]; } void update(int x) { if (x == 0) return; // cout << "update " << st[x] << " " << x << "\n"; update(1, 1, tt, tin[st[x]], tin[x]); update(p[st[x]]); // cout << "new: " << res << "\n"; } void dfs(int x, int p) { ::p[x] = p; c[x] = (v[x].size() == 1); sz[x] = 1; k += c[x]; for (auto to : v[x]) { if (to == p) continue; dfs(to, x); sz[x] += sz[to]; c[x] += c[to]; } // res += (x == root ? 0 : c[x] ^ 1); } void solve() { cin >> n >> q; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; v[a].push_back(b); v[b].push_back(a); } for (int i = 1; i <= n; i++) { if (v[i].size() > 1) { root = i; break; } } // cout << root << "\n"; dfs(root, 0); st[root] = root; trace(root, 0); build(1, 1, tt); for (int i = 1; i <= n; i++) { if (c[i] % 2 == 0) { // cout << "i: " << c[i] << "\n"; update(1, 1, tt, tin[i], tin[i]); } } // cout << res << "\n"; // cout << "kerima\n"; // return; while (q--) { int d; cin >> d; vector<int> g(d); for (auto &i : g) { cin >> i; k++; f[i]++; if (v[i].size() + f[i] == 2) { k--; continue; } update(i); } // cout << "Res: " << res << "\n"; cout << (k % 2 ? -1 : res + n - 2 + d) << "\n"; for (auto &i : g) { f[i]--; k--; if (v[i].size() + f[i] == 1) { k++; continue; } update(i); } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // debugMode(); int $ = 1; // cin >> $; while ($--) { solve(); } }
#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...