Submission #1228131

#TimeUsernameProblemLanguageResultExecution timeMemory
1228131TurkhuuSpring cleaning (CEOI20_cleaning)C++20
0 / 100
1093 ms7236 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (auto i = (a); i <= (b); i++) #define ROF(i, a, b) for (auto i = (a); i >= (b); i--) using namespace std; using ll = long long; const int N = 1e5 + 5; bool seen[N]; int par[N], sz[N]; vector<int> ch[N]; void dfs(int x) { sz[x] = 1; for (int y : ch[x]) { ch[y].erase(find(ch[y].begin(), ch[y].end(), par[y] = x)); dfs(y); sz[x] += sz[y]; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; FOR(i, 1, n - 1) { int a, b; cin >> a >> b; ch[a].push_back(b); ch[b].push_back(a); } dfs(1); int leaf = 0, even = 0; FOR(i, 1, n) { if (sz[i] % 2 == 0) even++; if (ch[i].size() + (i != 1) == 1) leaf++; } while (q--) { int D; cin >> D; int new_leaf = leaf + D; vector<int> a(D); for (auto& x : a) { cin >> x; for (int y = x; y != 1; y = par[y]) { even += sz[y] % 2 == 0 ? -1 : 1; sz[y]++; } if (!seen[x]) { seen[x] = 1; if (ch[x].size() + (x != 1) == 1) new_leaf--; } } cout << (new_leaf % 2 ? -1 : n - 1 + D + even) << "\n"; for (int x : a) { for (int y = x; y != 1; y = par[y]) { even += sz[y] % 2 == 0 ? -1 : 1; sz[y]--; } seen[x] = 0; } } return 6/22; }
#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...