Submission #305049

#TimeUsernameProblemLanguageResultExecution timeMemory
305049nicolaalexandraSpring cleaning (CEOI20_cleaning)C++14
100 / 100
623 ms30192 KiB
#include <bits/stdc++.h> #define DIM 100010 using namespace std; int whatChain[DIM],chainFatherNode[DIM],level[DIM],positionInChain[DIM],Size[DIM]; int frunza[DIM],f[DIM],mrk[DIM],fth[DIM],g[DIM],v[DIM]; vector <int> chains[DIM],L[DIM]; set <int> w; int nr_chains,n,q,i,j,x,y,m,rad,sol,sum; struct segment_tree{ int cnt; /// cate noduri au nr par de frunze in subarborele lor int lazy; }; vector <segment_tree> aint[DIM]; void dfs (int nod, int tata){ Size[nod] = 1; level[nod] = 1 + level[tata]; fth[nod] = tata; int ok = 0; for (auto vecin : L[nod]) if (vecin != tata){ ok = 1; dfs (vecin,nod); Size[nod] += Size[vecin]; f[nod] += f[vecin]; /// cate frunze am in subarborele lui nod } if (!ok){ nr_chains++; chains[nr_chains].push_back(0); chains[nr_chains].push_back(nod); positionInChain[nod] = 1; whatChain[nod] = nr_chains; f[nod] = frunza[nod] = 1; } else { int maxi = 0, heavy_son = 0; for (auto vecin : L[nod]){ if (vecin == tata) continue; if (Size[vecin] > maxi) maxi = Size[vecin], heavy_son = vecin; } chains[whatChain[heavy_son]].push_back(nod); whatChain[nod] = whatChain[heavy_son]; positionInChain[nod] = chains[whatChain[heavy_son]].size()-1; for (auto vecin : L[nod]){ if (vecin != tata && vecin != heavy_son) chainFatherNode[whatChain[vecin]] = nod; }}} void build (int chain, int nod, int st, int dr){ if (st == dr){ if (f[chains[chain][st]] % 2 == 0) /// are nr par de frunze aint[chain][nod].cnt = 1; return; } int mid = (st+dr)>>1; build (chain,nod<<1,st,mid); build (chain,(nod<<1)|1,mid+1,dr); aint[chain][nod].cnt = aint[chain][nod<<1].cnt + aint[chain][(nod<<1)|1].cnt; } void update_lazy (int chain, int nod, int st, int dr){ if (!aint[chain][nod].lazy) return; if (st != dr){ int fiu_st = nod<<1, fiu_dr = (nod<<1)|1, mid = (st+dr)>>1; aint[chain][fiu_st].cnt = mid - st + 1 - aint[chain][fiu_st].cnt; aint[chain][fiu_st].lazy = 1 - aint[chain][fiu_st].lazy; aint[chain][fiu_dr].cnt = dr - mid - aint[chain][fiu_dr].cnt; aint[chain][fiu_dr].lazy = 1 - aint[chain][fiu_dr].lazy; } aint[chain][nod].lazy = 0; } void update (int chain, int nod, int st, int dr, int x, int y){ update_lazy (chain,nod,st,dr); if (x <= st && dr <= y){ /// trb sa dau reverse sol -= aint[chain][nod].cnt; aint[chain][nod].cnt = (dr - st + 1) - aint[chain][nod].cnt; sol += aint[chain][nod].cnt; aint[chain][nod].lazy = 1; update_lazy (chain,nod,st,dr); return; } int mid = (st+dr)>>1; if (x <= mid) update (chain,nod<<1,st,mid,x,y); if (y > mid) update (chain,(nod<<1)|1,mid+1,dr,x,y); update_lazy (chain,nod<<1,st,mid); update_lazy (chain,(nod<<1)|1,mid+1,dr); aint[chain][nod].cnt = aint[chain][nod<<1].cnt + aint[chain][(nod<<1)|1].cnt; } void update_heavy (int x, int y){ if (whatChain[x] == whatChain[y]){ int posx = positionInChain[x], posy = positionInChain[y]; if (posx > posy) swap (posx,posy); update (whatChain[x],1,1,chains[whatChain[x]].size()-1,posx,posy); return; } if (level[chainFatherNode[whatChain[x]]] <= level[chainFatherNode[whatChain[y]]]) swap (x,y); update (whatChain[x],1,1,chains[whatChain[x]].size()-1,positionInChain[x],chains[whatChain[x]].size()-1); int nr = chainFatherNode[whatChain[x]]; update_heavy (nr,y); } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>q; for (i=1;i<n;i++){ cin>>x>>y; L[x].push_back(y); L[y].push_back(x); g[x]++, g[y]++; } for (i=1;i<=n;i++) if (g[i] > 1){ rad = i; break; } dfs (rad,0); for (i=1;i<=nr_chains;i++){ aint[i].resize(chains[i].size()*4); build (i,1,1,chains[i].size()-1); sum += aint[i][1].cnt; } for (;q--;){ cin>>m; /// calculez nr de frunze int nr = f[rad] + m; w.clear(); for (i=1;i<=m;i++){ cin>>v[i]; if (frunza[v[i]] && !mrk[v[i]]) /// asta nu o sa mai fie frunza nr--; mrk[v[i]]++; w.insert(v[i]); } if (nr % 2){ cout<<"-1\n"; for (i=1;i<=m;i++) mrk[v[i]]--; continue; } sol = n + m - 2 + sum; for (auto it : w){ if (frunza[it]){ if (mrk[it] % 2 == 0) update_heavy (it,rad); } else { if (mrk[it] % 2) update_heavy (it,rad); } } /*if (m == 2){ for (i=1;i<=nr_chains;i++) cout<<aint[i][1].cnt<<" "; cout<<endl; }*/ //for (i=1;i<=nr_chains;i++) /// o sa mi iau tle pe asta da csf // sol += aint[i][1].cnt; cout<<sol<<"\n"; /// reintializez vectorul si refac aintul for (auto it : w){ if (frunza[it]){ if (mrk[it] % 2 == 0) update_heavy (it,rad); } else { if (mrk[it] % 2) update_heavy (it,rad); } } for (i=1;i<=m;i++) mrk[v[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...