Submission #1217037

#TimeUsernameProblemLanguageResultExecution timeMemory
1217037anonymous321Spring cleaning (CEOI20_cleaning)C++20
34 / 100
1097 ms16200 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int>> adj_list; vector<int> nleafs; vector<int> dp; vector<int> dpl; void dfs (int v, int p) { dp[v] = 0; dpl[v] = 0; int cnt = 0; for (auto &it : adj_list[v]) { if (it == p) continue; cnt++; dfs(it, v); dpl[v] += dpl[it]; dp[v] += 2 - (dpl[it] % 2); dp[v] += dp[it]; } if (cnt == 0 && nleafs[v] == 0) dpl[v]++; if (cnt + nleafs[v] <= 1 && p == -1) dpl[v]++; dpl[v] += nleafs[v]; dp[v] += nleafs[v]; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; adj_list = vector<vector<int>> (n); for (int i = 0; i < n-1; i++) { int u, v; cin >> u >> v; adj_list[u-1].push_back(v-1); adj_list[v-1].push_back(u-1); } vector<vector<int>> va (q); for (int i = 0; i < q; i++) { int d; cin >> d; for (int j = 0; j < d; j++) { int a; cin >> a; va[i].push_back(a-1); } } nleafs = vector<int> (n, 0); dp = vector<int> (n, 0); dpl = vector<int> (n, 0); for (int i = 0; i < q; i++) { for (auto &it: va[i]) { nleafs[it]++; } dfs(0, -1); if (dpl[0] % 2 == 1) dp[0] = -1; cout << dp[0] << "\n"; for (auto &it: va[i]) { nleafs[it]--; } } return 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...