Submission #878165

#TimeUsernameProblemLanguageResultExecution timeMemory
878165AlishSpring cleaning (CEOI20_cleaning)C++17
26 / 100
492 ms22596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define F first #define S second #define pb push_back #define endl '\n' #define Mp make_pair #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " = " << x << endl; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout); ll mod = 1e9+7 ; const int N = 1e5+23; vector<int> g[N]; int par[N], head[N], h[N], sz[N], bi[N], pos[N]; // hld int seg[4*N], lpz[4*N], st[N], ft[N], tim;//segment int n, q; int is[N]; void DFS(int v, int p=0){ int Mx=0; sz[v]=1; for (int u: g[v]){ if(u==p) continue; h[u]=h[v]+1; par[u]=v; DFS(u, v); if(sz[u]>Mx){ bi[v]=u; Mx=sz[u]; } sz[v]+=sz[u]; is[v]+=is[u]; } } void dfs(int v, int p=0){ st[v]=tim; pos[st[v]]=v; tim++; if(!p) head[v]=v; if(bi[v]){ head[bi[v]]=head[v]; dfs(bi[v], v); } for (int u: g[v]){ if(u==p || u==bi[v]) continue; head[u]=u; dfs(u, v); } ft[v]=tim; } void Shift(int l, int r, int ind){ if(r-l==1) return; if(!lpz[ind]) return ; int mid=(r+l)>>1; seg[2*ind+1]=mid-l-seg[2*ind+1]; seg[2*ind+2]=r-mid-seg[2*ind+2]; lpz[2*ind+1]^=1; lpz[2*ind+2]^=1; lpz[ind]=0; } void build(int l=0, int r=n, int ind=0){ if(r-l==1){ if(is[pos[l]]%2==0) seg[ind]=1; return; } int mid=(r+l)>>1; build(l, mid, 2*ind+1); build(mid, r, 2*ind+2); seg[ind]=seg[2*ind+1]+seg[2*ind+2]; } void upd(int lx, int rx, int l=0, int r=n, int ind=0){ Shift(l, r, ind); if(lx>=r || rx<=l) return; if(lx<=l && rx>=r){ seg[ind]=r-l-seg[ind]; lpz[ind]^=1; return; } int mid=(r+l)>>1; upd(lx, rx, l, mid, 2*ind+1); upd(lx, rx, mid, r, 2*ind+2); seg[ind]=seg[2*ind+1]+seg[2*ind+2]; } void updd(int v, int u){ while(head[u]!=head[v]){ if(h[head[u]] < h[head[v]]) swap(u, v); upd(st[head[u]], st[u]+1); u=par[head[u]]; } if(h[v]>h[u]) swap(u, v); upd(st[v], st[u]+1); } int main() { fast_io cin>>n>>q; for (int i=0; i<n-1; i++){ int u, v; cin>>v>>u; g[v].pb(u); g[u].pb(v); } int r=0; int leaf=0; for (int i=1; i<=n; i++){ if(g[i].size()==1) {leaf++; is[i]=1; } else r=i; } DFS(r); dfs(r); build(); while(q--){ vector<int> d; int k; cin>>k; for (int i=0; i<k; i++) { int p; cin>>p; d.pb(p); } leaf+=k; for (auto pp: d) if(g[pp].size()==1) {leaf--; updd(r, pp);} for (auto pp: d) updd(r, pp); if(leaf&1)cout<<-1<<endl; else cout<<n+k-1+seg[0]-1<<endl; leaf-=k; for (auto pp: d) if(g[pp].size()==1) {leaf++; updd(r, pp);} for (auto pp: d) updd(r, pp); } }
#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...