Submission #1215308

#TimeUsernameProblemLanguageResultExecution timeMemory
1215308KindaGoodGamesSpring cleaning (CEOI20_cleaning)C++17
28 / 100
1097 ms11200 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; const int MAXN = 1e5; int n; vector<vector<int>> adj; int par[MAXN]; int leaf[MAXN]; int dp[MAXN]; void DFS(int v, int p){ dp[v] = 0; par[v] = p; if(adj[v].size() == 1){ dp[v]++; leaf[v] = true; } for(auto u : adj[v]){ if(u == p) continue; DFS(u,v); 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(node)){ oldDP[node] = dp[node]; } dp[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); 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; } } DFS(r,r); 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...