Submission #987102

#TimeUsernameProblemLanguageResultExecution timeMemory
987102aykhnSpring cleaning (CEOI20_cleaning)C++17
34 / 100
1051 ms22612 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F const int MXN = 2e5 + 5; int n, q, r; vector<int> adj[MXN]; int cnt[MXN], add[MXN], leaf, res; void dfs(int a, int p) { cnt[a] = 0; int f = 1; for (int v : adj[a]) { if (v == p) continue; f = 0; dfs(v, a); cnt[a] += cnt[v]; if (cnt[v] & 1) res++; else res += 2; } leaf += f; cnt[a] += f; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; i++) { if (adj[i].size() >= 2) { r = i; break; } } for (int i = 1; i <= q; i++) { set<int> s; int d; cin >> d; for (int j = 1; j <= d; j++) { int x; cin >> x; add[x]++; s.insert(x); } int m = n; for (int j = 1; j <= m; j++) { for (int k = 1; k <= add[j]; k++) { adj[j].push_back(++n); } } res = leaf = 0; dfs(r, r); if (leaf & 1) cout << -1 << '\n'; else cout << res << '\n'; for (int j = 1; j <= m; j++) { for (int k = 1; k <= add[j]; k++) { adj[j].pop_back(), n--; } add[j] = 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...