Submission #1218214

#TimeUsernameProblemLanguageResultExecution timeMemory
1218214__moin__Spring cleaning (CEOI20_cleaning)C++20
0 / 100
191 ms9424 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); vector<int> par_pref(2e5); vector<int> neg_par_pref(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); function<void(int,int,int,int)> dfs_par = [&](int v, int p, int pref, int neg_pref) { par_pref[v] = pref + par[v]; neg_par_pref[v] = neg_pref + 1 - par[v]; for (int nn : adj[v]) { if (nn != p) { dfs_par(nn, v, par_pref[v], neg_par_pref[v]); } } }; dfs_par(0, -1, 0, 0); // 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--; if (par[0] + (adj[x].size() != 1)) cout << -1 << "\n"; else { // if (adj[x].size() != 1) // cout << (dp[0] - 2 + par[0]) - neg_par_pref[x] + par_pref[x] << "\n"; cout << (dp[0] - 2 + par[0]) + 1 << "\n"; } // 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...