Submission #1215305

#TimeUsernameProblemLanguageResultExecution timeMemory
1215305KindaGoodGamesSpring cleaning (CEOI20_cleaning)C++17
0 / 100
1097 ms7412 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define tiii tuple<int,int,int> using namespace std; int n; vector<vector<int>> adj; vector<int> par; vector<bool> leaf; vector<int> dp; void DFS(int v, int p, vector<int>& dp, vector<int>& arr){ dp[v] = arr[v]; par[v] = p; if(adj[v].size() == 1 && arr[v] == 0){ dp[v]++; leaf[v] = true; } for(auto u : adj[v]){ if(u == p) continue; DFS(u,v,dp,arr); dp[v] += dp[u]; } } int solve(int d, int r){ map<int, int> oldDP; set<int> oldL; for(int i = 0; i < d; i++){ int a; cin >> a; a--; if(leaf[a]){ leaf[a] = false; oldL.insert(a); continue; } int node = a; while(par[node] != node){ if(!oldDP.count(par[node])){ oldDP[par[node]] = dp[par[node]]; } dp[par[node]]++; node = par[node]; } if(!oldDP.count(node)){ oldDP[node] = dp[node]; } dp[node]++; } int cnt = 0; for(int i = 0; i < n; i++){ if(dp[i] % 2 == 0){ cnt++; } } int dpr = dp[r]; // we remove the new leafs for(auto l : oldL){ leaf[l] = true; } // reset dp values for(auto p : oldDP){ dp[p.first] = p.second; } if(dpr % 2 == 1){ return -1; } return n + d + cnt - 2; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int q; cin >> n>> q; adj.resize(n); par.resize(n); for(int i = 0; i < n-1; i++){ int a,b; cin >> a >> b; a--;b--; adj[a].push_back(b); adj[b].push_back(a); } int r = 0; for(int i = 0; i < n; i++){ if(adj[i].size() > 1){ r = i; break; } } dp.resize(n); vector<int> EMPTY(n); leaf.resize(n); DFS(r,r,dp,EMPTY); while(q--){ int d; cin >> d; cout << solve(d, r) << "\n"; } }
#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...