Submission #1262129

#TimeUsernameProblemLanguageResultExecution timeMemory
1262129abdelhakimSpring cleaning (CEOI20_cleaning)C++20
35 / 100
228 ms327680 KiB
#include <bits/stdc++.h> #define ll long long #define dbg(x) cerr << #x << ' ' << x << endl; #define inf 1e18 using namespace std; void printvec(vector<ll>& vec) { for (auto &&e : vec) { cout << e << ' '; } cout << endl; } const int maxn = 1e5; int value[maxn]; int in[maxn]; int out[maxn]; int arr2[maxn]; const int lg=18; int up[maxn][lg]; ll solve(vector<vector<ll>>& adj, ll node, ll par, ll& ans,vector<pair<ll,ll>>& parr) { if(node!=par && adj[node].size()==1) { parr[node]={par,1}; if(node!=0) { if(parr[node].second==0) ans+=2; else ans++; } return 1; } ll sm=0; for (auto &&e : adj[node]) { if(e==par)continue; ll val=solve(adj,e,node,ans,parr); sm+=val; } if(adj[node].size()==1 && node==0) sm++; parr[node]={par,sm%2}; if(node!=0) { if(parr[node].second==0) ans+=2; else ans++; } return sm; } void dfs(ll node, ll par, ll cur,vector<vector<ll>>& adj, vector<pair<ll,ll>>& parr, ll& time) { in[node]=time; if(node!=0) { if(parr[node].second) { cur++; } else cur--; } value[node]=cur; for (auto &&e : adj[node]) { if(e==par) continue; time++; dfs(e,node,cur,adj,parr,time); } out[node] = time; } void gadup(ll n, vector<pair<ll,ll>>& parr) { for (int i=0;i<n;i++) { for (int j=0;j<lg;j++) { if(j==0) { up[i][j]=parr[i].first; } else { up[i][j]=up[up[i][j-1]][j-1]; } } } } bool islca(ll a, ll b) { if(in[a] <= in[b] && in[b] <= out[a]) return true; return false; } ll lca(ll u, ll v) { if(islca(u,v)) return u; if(islca(v,u)) return v; for (int j=lg-1;j>=0;j--) { if(!(islca(up[u][j],v))) { u=up[u][j]; } } u=up[u][0]; return u; } ll dfs2(ll& ans, ll node, ll par, vector<vector<ll>>& adj) { if(node!=0 && adj[node].size()==1) return arr2[node]; ll val=arr2[node]; for (auto &&e : adj[node]) { if(e==par) continue; ll qry=dfs2(ans,e,node,adj); val+=qry; if(qry%2) { ans+=value[e]-value[node]; } } return val; } int main() { cin.tie(0); ios_base::sync_with_stdio(false); ll n, q; cin>>n>>q; for (int i=0;i<maxn;i++) { arr2[i]=0; } vector<vector<ll>> adj(n); value[0]=0; for (int i=0;i<n-1;i++) { ll u, v; cin>>u>>v; u--;v--; adj[u].push_back(v); adj[v].push_back(u); } ll old=0; ll leaves=0; for (int i=0;i<n;i++) { leaves+=adj[i].size()==1; } vector<pair<ll,ll>> parr(n); solve(adj,0,0,old,parr); ll time=0; dfs(0,0,0,adj,parr,time); gadup(n,parr); vector<vector<ll>> adj2(n); while(q--) { ll d; cin>>d; vector<ll> v; vector<ll> arr; ll ans=old; ll val=leaves; for (int i=0;i<d;i++) { ll nd; cin>>nd; nd--; arr.push_back(nd); } auto comp=[&](ll a, ll b){return in[a]<in[b];}; sort(arr.begin(), arr.end(),comp); ll cur=0; for (int i=0;i<d;i++) { cur++; if(i==d-1 || arr[i+1]!=arr[i]) { if(adj[arr[i]].size()==1) { cur--; } if(cur%2) v.push_back(arr[i]); cur=0; } } val+=v.size(); if(val%2) cout<<-1<<endl; else { ans+=d; vector<ll> v2; for (auto &&e : v) { arr2[e]=1; v2.push_back(e); } ll sz=v.size(); for (int i=0;i<sz-1;i++) { v.push_back(lca(v[i],v[i+1])); } v.push_back(0); vector<ll> nodes=v; sort(nodes.begin(), nodes.end(), comp); nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end()); // add required LCAs of consecutive nodes vector<ll> aug = nodes; for (int i=0;i+1<(int)nodes.size();++i) aug.push_back(lca(nodes[i], nodes[i+1])); sort(aug.begin(), aug.end(), comp); aug.erase(unique(aug.begin(), aug.end()), aug.end()); // build with stack vector<ll> st; st.push_back(aug[0]); for (int i=1;i<(int)aug.size();++i) { ll x = aug[i], g = lca(x, st.back()); while (st.size() >= 2 && !islca(st[st.size()-2], x)) { // connect st.back() -> st[st.size()-2] ll u = st.back(); st.pop_back(); adj2[st.back()].push_back(u); adj2[u].push_back(st.back()); } if (st.back() != g) { // connect st.back() -> g ll u = st.back(); st.pop_back(); adj2[g].push_back(u); adj2[u].push_back(g); if (st.empty() || st.back() != g) st.push_back(g); } st.push_back(x); } while (st.size() >= 2) { ll u = st.back(); st.pop_back(); adj2[st.back()].push_back(u); adj2[u].push_back(st.back()); } dfs2(ans,0,0,adj2); cout << ans << endl; for (auto &&e : v) { adj2[e].clear(); } for (auto &&e : v2) { arr2[e]=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...