Submission #1230062

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