Submission #1230044

#TimeUsernameProblemLanguageResultExecution timeMemory
1230044RakhimovAmirSpring cleaning (CEOI20_cleaning)C++20
9 / 100
37 ms7612 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], k; int res, root; void dfs(int x, int p) { ::p[x] = p; c[x] = (v[x].size() == 1); k += c[x]; for (auto to : v[x]) { if (to == p) continue; dfs(to, x); c[x] += c[to]; } c[x] %= 2; if (c[x] == 0) c[x] = 2; res += (x == root ? 0 : c[x]); } void update(int x) { if (x == root) return; res -= c[x]; if (c[x] == 2) c[x] = 1; else c[x] = 2; res += c[x]; } 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, root); while (q--) { int d; cin >> d; vector<int> g(d); for (auto &i : g) { cin >> i; if (v[i].size() + f[i] == 1) { f[i]++; continue; } f[i]++; update(i); k++; } cout << (k % 2 ? -1 : res + d) << "\n"; for (auto &i : g) { f[i]--; if (v[i].size() + f[i] == 1) { continue; } update(i); k--; } } } 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...