제출 #1123881

#제출 시각아이디문제언어결과실행 시간메모리
1123881kikaxe4781Spring cleaning (CEOI20_cleaning)C++17
100 / 100
250 ms24628 KiB
#include<bits/stdc++.h> #define ll long long #define ldb long double #define fi first #define se second #define pir pair<int,int> using namespace std; const int maxn = 2e5 + 5; template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;} template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;} struct segment_tree{ int seg[4*maxn]; bool lazy[4*maxn]; void downlazy(int v,int l,int r){ if (!lazy[v]) return; seg[v] = (r - l + 1) - seg[v]; if (l != r){ lazy[2*v + 1] ^= 1; lazy[2*v + 2] ^= 1; } lazy[v] = 0; } void update(int l,int r,int v,int lx,int rx,int val){ downlazy(v,l,r); if (l > rx || r < lx) return; if (l >= lx && r <= rx){ lazy[v] ^= val; downlazy(v,l,r); return; } int w = (l + r)/2; update(l,w,2*v + 1,lx,rx,val); update(w + 1,r,2*v + 2,lx,rx,val); seg[v] = seg[2*v + 1] + seg[2*v + 2]; } int calc(int l,int r,int v,int lx,int rx){ downlazy(v,l,r); if (l > rx || r < lx) return 0; if (l >= lx && r <= rx) return seg[v]; int w = (l + r)/2; return calc(l,w,2*v + 1,lx,rx) + calc(w + 1,r,2*v + 2,lx,rx); } } seg; vector <int> Q[maxn],vec[maxn]; pir pos[maxn]; int chain[maxn],D[maxn],mx[maxn],father[maxn],deg[maxn]; void input(int n,int q){ for (int i = 1 ; i < n ; i++){ int u,v; cin >> u >> v; vec[u].push_back(v); vec[v].push_back(u); } for (int id = 1 ; id <= q ; id++){ int len; cin >> len; Q[id].resize(len); for (int i = 0 ; i < len ; i++) cin >> Q[id][i]; } } int get_root(int n){ for (int i = 1 ; i <= n ; i++) if (vec[i].size() >= 2) return i; return 1; } void dfs(int u,int par){ mx[u] = D[u]; for (int v : vec[u]) if (v != par){ deg[u]++; D[v] = D[u] + 1; father[v] = u; dfs(v,u); maxi(mx[u],mx[v]); } } void HLD_dfs(int u,int par,bool state,int &m){ pos[u].fi = ++m; chain[u] = (state) ? u : chain[par]; int nxt = 0; for (int v : vec[u]) if (v != par && mx[v] == mx[u]){ nxt = v; break; } if (nxt > 0) HLD_dfs(nxt,u,0,m); for (int v : vec[u]) if (v != par && v != nxt) HLD_dfs(v,u,1,m); pos[u].se = m; } void HLD_update(int u,int n,int val){ while (D[u] >= 1){ seg.update(1,n,0,pos[chain[u]].fi,pos[u].fi,val); u = father[chain[u]]; } } void prepare(int root,int n){ D[root] = 1; dfs(root,0); int m = 0; HLD_dfs(root,0,1,m); //prepare leaf for (int u = 1 ; u <= n ; u++) if (vec[u].size() == 1) HLD_update(u,n,1); } void add_to_tree(int id,int n){ for (int u : Q[id]){ deg[u]++; if (deg[u] > 1) HLD_update(u,n,1); } } void clean_up(int id,int n){ for (int u : Q[id]){ if (deg[u] > 1) HLD_update(u,n,1); deg[u]--; } } int get_answer(int root,int id,int n){ add_to_tree(id,n); int N = Q[id].size() + n; int parity = seg.calc(1,n,0,pos[root].fi,pos[root].fi); int cnt = seg.calc(1,n,0,1,n) + Q[id].size(); clean_up(id,n); if (parity) return -1; return cnt + 2*(N - 1 - cnt); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); // freopen("CLEANING.inp","r",stdin); // freopen("CLEANING.out","w",stdout); int n,q; cin >> n >> q; input(n,q); int root = get_root(n); prepare(root,n); for (int id = 1 ; id <= q ; id++) cout << get_answer(root,id,n) << "\n"; 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...