Submission #1218206

#TimeUsernameProblemLanguageResultExecution timeMemory
1218206__moin__Spring cleaning (CEOI20_cleaning)C++20
28 / 100
1095 ms21492 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long const int INF = 1e9; int clamp(int x) { return min(x, INF); } vector<int> dp(2e5); vector<bool> par(2e5); vector<int> parent(2e5); __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); } function<void(int,int)> dfs = [&](int v, int p) { parent[v] = p; 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]; } } par[v] = thispar; dp[v] = sum + (2 - par[v]); }; dfs(0, -1); // ONE QUERY ONLY for (int Q = 0; Q < q; Q++) { // auto adj_local = adj; int m; cin >> m; vector<int> revert(m); vector<bool> marked(n+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++); marked[n-1] = 1; while (x != -1) { marked[x] = 1; x = parent[x]; } } function<void(int,int)> dfs2 = [&](int v, int p) { if (!marked[v]) return; bool thispar = adj[v].size() == 1; int sum = 0; for (int nn : adj[v]) { if (nn != p) { dfs2(nn, v); thispar ^= par[nn]; sum += dp[nn]; } } par[v] = thispar; dp[v] = sum + (2 - par[v]); }; dfs2(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(); dfs2(0, -1); } 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...