Submission #985319

#TimeUsernameProblemLanguageResultExecution timeMemory
985319alexddSpring cleaning (CEOI20_cleaning)C++17
0 / 100
244 ms14204 KiB
#include<bits/stdc++.h> using namespace std; int n,q,root; vector<int> con[100005]; struct node { int cnt0,cnt1; int lazy; }; node aint[270000]; void propagate(int nod) { if(!aint[nod].lazy) return; aint[nod*2].lazy ^= 1; aint[nod*2+1].lazy ^= 1; swap(aint[nod*2].cnt0, aint[nod*2].cnt1); swap(aint[nod*2+1].cnt0, aint[nod*2+1].cnt1); aint[nod].lazy=0; } void upd(int nod, int st, int dr, int le, int ri) { if(le>ri) return; if(le==st && dr==ri) { aint[nod].lazy ^= 1; swap(aint[nod].cnt0, aint[nod].cnt1); return; } propagate(nod); int mij=(st+dr)/2; upd(nod*2,st,mij,le,min(mij,ri)); upd(nod*2+1,mij+1,dr,max(mij+1,le),ri); aint[nod].cnt0 = aint[nod*2].cnt0 + aint[nod*2+1].cnt0; aint[nod].cnt1 = aint[nod*2].cnt1 + aint[nod*2+1].cnt1; } int siz[100005]; int cntf[100005]; int head[100005]; int parent[100005]; int depth[100005]; int pos[100005],curpos; void dfs(int nod) { siz[nod]=1; for(auto adj:con[nod]) { if(adj!=parent[nod]) { parent[adj]=nod; depth[adj]=depth[nod]+1; dfs(adj); cntf[nod] += cntf[adj]; siz[nod] += siz[adj]; } } if(cntf[nod]==0) cntf[nod]=1; } void decompose(int nod, int chead) { pos[nod]=++curpos; head[nod]=chead; int heavy=-1,maxc=-1; for(auto adj:con[nod]) if(adj!=parent[nod] && siz[adj]>maxc) maxc=siz[adj], heavy=adj; if(heavy!=-1) decompose(heavy,chead); for(auto adj:con[nod]) if(adj!=parent[nod] && adj!=heavy) decompose(adj,adj); } void hld_upd(int a) { for(;head[a]!=root;a=parent[head[a]]) { upd(1,1,n,pos[head[a]],pos[a]); } upd(1,1,n,pos[root],pos[a]); } int aux[100005]; int visited[100005]; void build(int nod, int st, int dr) { if(st==dr) { aint[nod].cnt0=1; return; } int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); aint[nod].cnt0 = aint[nod*2].cnt0 + aint[nod*2+1].cnt0; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>q; int u,v; for(int i=1;i<n;i++) { cin>>u>>v; con[u].push_back(v); con[v].push_back(u); } for(int i=1;i<=n;i++) { if((int)con[i].size()>1) { root=i; break; } } dfs(root); decompose(root,root); build(1,1,n); for(int i=1;i<=n;i++) if(cntf[i]%2==1) upd(1,1,n,pos[i],pos[i]); for(int pas=1;pas<=q;pas++) { int nr,auxf=0; cin>>nr; for(int i=1;i<=nr;i++) { cin>>aux[i]; hld_upd(aux[i]); if(cntf[aux[i]]==1 && visited[aux[i]]!=pas) visited[aux[i]]=pas; else auxf++; } if((cntf[root]+auxf)%2==1) cout<<-1<<"\n"; else cout<<aint[1].cnt0*2 + aint[1].cnt1 - 2 + nr<<"\n"; for(int i=1;i<=nr;i++) hld_upd(aux[i]); } 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...