Submission #1234958

#TimeUsernameProblemLanguageResultExecution timeMemory
1234958t_hollSpring cleaning (CEOI20_cleaning)C++20
34 / 100
1095 ms22724 KiB
#include <bits/stdc++.h> #define int long long #define MULTITEST false using namespace std; const int INF = 1e18; vector<int> vp; vector<vector<int>> roads; pair<int, int> compute (int node, int parent) { vector<int> dp1, dp2; int oblig = 0; int oblig_cnt = 0; for (int next : roads[node]) if (next != parent) { pair<int, int> sub = compute(next, node); if (sub.first == INF) { oblig += sub.second; oblig_cnt += 2; } else if (sub.second == INF) { oblig += sub.first; oblig_cnt ++; } else { dp1.push_back(sub.first); dp2.push_back(sub.second); } } for (int i = 0; i < vp[node]; i ++) { oblig ++; oblig_cnt ++; } if (dp1.size() + oblig_cnt == 0) { return { 1, INF }; } vp[node] = 0; int mvr = 0; for (int u : dp1) mvr = u; int mpr = INF; for (int i = 0; i < dp1.size(); i ++) mpr = min(mpr, dp2[i] - dp1[i]); int np1 = mvr + oblig; int np2 = mvr + mpr + oblig; if (((dp1.size() + oblig_cnt) & 1) == 0) swap(np1, np2); np1 ++; np2 += 2; if (np1 >= INF) np1 = INF; if (np2 >= INF) np2 = INF; assert(np1 == INF || np2 == INF); return { np1, np2 }; } void solve () { int N, Q; cin >> N >> Q; vp.resize(N); roads.resize(N); vector<int> deg(N); for (int i = 1; i < N; i ++) { int a, b; cin >> a >> b; a --; b --; roads[a].push_back(b); roads[b].push_back(a); deg[a] ++; deg[b] ++; } int root = 0; for (; root < N; root ++) if (deg[root] != 1) break ; for (int i = 0; i < Q; i ++) { int d; cin >> d; for (int j = 0; j < d; j ++) { int x; cin >> x; x --; vp[x] ++; } pair<int, int> U = compute(root, -1); int res = U.second; if (res >= INF) cout << -1 << "\n"; else cout << (res - 2) << "\n"; } } signed main () { ios_base::sync_with_stdio(false); cin.tie(NULL); int T = 1; if (MULTITEST) cin >> T; for (int t = 0; t < T; t ++) 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...