Submission #558073

#TimeUsernameProblemLanguageResultExecution timeMemory
558073status_codingSpring cleaning (CEOI20_cleaning)C++14
0 / 100
1087 ms9676 KiB
#include <bits/stdc++.h> using namespace std; int n,q,sz,root; int cntEven; int nrLeaf[100005]; int aux[100005]; int parV[100005]; vector<int> v[100005]; vector<int> upd; void dfs(int p, int par) { parV[p] = par; nrLeaf[p] = 0; for(int it : v[p]) { if(it == par) continue; dfs(it, p); nrLeaf[p] += nrLeaf[it]; } nrLeaf[p] += aux[p]; if(!nrLeaf[p]) nrLeaf[p] = 1; if(nrLeaf[p] % 2 == 0) cntEven++; } void solveBig(int k, vector<int> &upd) { for(int it : upd) aux[it] ++; cntEven=0; dfs(root, 0); if(nrLeaf[root] % 2) cout<<"-1\n"; else cout<<n+k-1 + cntEven-1<<'\n'; for(int i=1; i<=n; i++) aux[i] = 0; cntEven=0; dfs(root, 0); } void add(int p) { if((int)v[p].size() == 1) return; while(p) { nrLeaf[p]++; if(nrLeaf[p] % 2 == 0) cntEven++; else cntEven--; p = parV[p]; } } void del(int p) { if((int)v[p].size() == 1) return; while(p) { nrLeaf[p]--; if(nrLeaf[p] % 2 == 0) cntEven++; else cntEven--; p = parV[p]; } } void solveSmall(int k, vector<int> &upd) { for(int it : upd) add(it); if(nrLeaf[root] % 2) cout<<"-1\n"; else cout<<n+k-1 + cntEven-1<<'\n'; for(int it : upd) del(it); } int main() { cin>>n>>q; //sz = sqrt((int)1e5); //sz=0; sz = 1e9; for(int i=1; i<n; i++) { int x, y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } for(int i=1; i<=n; i++) if((int)v[i].size() >= 2) root = i; cntEven=0; dfs(root, 0); while(q) { q--; upd.clear(); int k; cin>>k; for(int i=1; i<=k; i++) { int x; cin>>x; upd.push_back(x); } if(k >= sz) solveBig(k, upd); else solveSmall(k, upd); } 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...