Submission #485799

#TimeUsernameProblemLanguageResultExecution timeMemory
485799radalSpring cleaning (CEOI20_cleaning)C++14
100 / 100
238 ms34488 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O2") #pragma GCC target("avx2,fma") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; typedef pair<long double,long double> pld; const long long int N = 2e5+10,mod = 1e9+7,inf = 1e9,sq = 500,maxm = 1e5+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int n,ll k){ int c = 1; while (k){ if (k&1) c = (1ll*c*n)%mod; n = (1ll*n*n)%mod; k >>= 1; } return c; } vector<int> adj[N]; bool leaf[N],vis[N]; int ans,par[N][20],h[N],tin[N],T; int cnt[N][2],L[N],R[N]; void dfs(int v,int p){ par[v][0] = p; tin[v] = T; T++; for (int u : adj[v]){ if (u == p) continue; h[u] = h[v]+1; dfs(u,v); if (leaf[u]){ ans++; leaf[v] = !leaf[v]; } else ans += 2; } if(adj[v].size() == 1) leaf[v] = 1; } inline int lca(int u,int v){ if (h[u] > h[v]) swap(u,v); repr(i,19,0){ if (h[v]-h[u] >= (1 << i)) v = par[v][i]; } if (u == v) return v; repr(i,19,0){ if (par[u][i] != par[v][i]){ u = par[u][i]; v = par[v][i]; } } return par[u][0]; } void dfs2(int v){ for (int u : adj[v]){ if(u == par[v][0]) continue; cnt[u][0] = cnt[v][0]; cnt[u][1] = cnt[v][1]; cnt[u][leaf[u]]++; dfs2(u); } } int main(){ ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,q; cin >> n >> q; int r = -1; rep(i,1,n){ int u,v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); if (adj[u].size() == 2) r = u; else if (adj[v].size() == 2) r = v; } dfs(r,-1); dfs2(r); rep(j,1,19){ rep(i,1,n+1){ if (h[i] < (1 << j)) continue; par[i][j] = par[par[i][j-1]][j-1]; } } while (q--){ int t,out; cin >> t; out = ans+t; vector<int> ve; vector<pll> ve2; ve.reserve(t); rep(i,0,t){ int p; cin >> p; ve.pb(p); if (adj[p].size() > 1 || vis[p]) ve2.pb({tin[p],p}); else vis[p] = 1; } rep(i,0,t) vis[ve[i]] = 0; sort(ve2.begin(),ve2.end()); set<pll> st; set<int> st2; int sz = ve2.size(); if (leaf[r] != (sz&1)){ cout << -1 << endl; continue; } if (!sz){ cout << out << endl; continue; } rep(i,0,sz-1){ int w = lca(ve2[i].Y,ve2[i+1].Y); st.insert({-h[w],i}); st2.insert(i); L[i] = i-1; R[i] = i+1; } R[sz-1] = sz; st2.insert(sz-1); while (!st.empty()){ pll p = *(st.begin()); st.erase(st.begin()); int v = ve2[p.Y].Y; int u = ve2[R[p.Y]].Y; st2.erase(R[p.Y]); st2.erase(p.Y); int w = lca(u,v); out = out+(cnt[v][1]+cnt[u][1]-2*cnt[w][1])-(cnt[v][0]+cnt[u][0]-2*cnt[w][0]); if (L[p.Y] != -1){ R[L[p.Y]] = R[R[p.Y]]; st.erase({-h[lca(v,ve2[L[p.Y]].Y)],L[p.Y]}); } if (R[R[p.Y]] < sz){ L[R[R[p.Y]]] = L[p.Y]; st.erase({-h[lca(u,ve2[R[R[p.Y]]].Y)],R[p.Y]}); } if (L[p.Y] != -1 && R[R[p.Y]] < sz) st.insert({-h[lca(ve2[L[p.Y]].Y,ve2[R[R[p.Y]]].Y)],L[p.Y]}); } if (!st2.empty()){ int ind = *(st2.begin()); int u = ve2[ind].Y; out = out + cnt[u][1]-cnt[u][0]; } rep(i,0,sz-1) L[i] = R[i] = 0; cout << out << endl; } }
#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...