Submission #1218174

#TimeUsernameProblemLanguageResultExecution timeMemory
1218174__moin__Spring cleaning (CEOI20_cleaning)C++20
34 / 100
1095 ms21704 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long const int INF = 1e9; int clamp(int x) { return min(x, INF); } __int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n,q; cin >> n >> q; vector<vector<int>> adj(n); for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } // ONE QUERY ONLY for (int Q = 0; Q < q; Q++) { // auto adj_local = adj; int m; cin >> m; vector<int> revert(m); for (int i = 0; i < m; i++) { int x; cin >> x; x--; revert[i] = x; adj.push_back({x}); adj[x].push_back(n++); } vector<int> dp(n, INF); vector<bool> par(n); function<void(int,int)> dfs = [&](int v, int p) { // bool leaf = ; bool thispar = adj[v].size() == 1; int sum = 0; for (int nn : adj[v]) { if (nn != p) { dfs(nn, v); thispar ^= par[nn]; sum += dp[nn]; } } // if (leaf) { // thispar ^= 1; // sum += 1; // } // { par[v] = thispar; dp[v] = sum + (2 - par[v]); // } }; dfs(0, -1); if (par[0]) cout << -1 << "\n"; else cout << dp[0] - 2 + par[0] << "\n"; n -= m; adj.resize(n); for (int e : revert) adj[e].pop_back(); } 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...