Submission #1160337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160337		Kaztaev_Alisher	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	158 ms	22856 KiB

cleaning

#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;	

int P[N] , D[N] , H[N] , B[N] , pos[N] , NW;
int n , q , t[N*4] , a[N], b[N] , u[N*4] , sub[N] , cnt[N];
vector<int> g[N];  
void upd(int v, int tl , int tr , int pos , int val){
	if(tl == tr){
		t[v] = val;
		return;
	}
	int tm = (tl+tr) >> 1;
	if(tm >= pos) upd(v*2,tl,tm,pos,val);
	else upd(v*2+1,tm+1,tr,pos,val);
	t[v] = t[v*2]+t[v*2+1];
}
void push(int v, int tl ,int tr){
	if(tl == tr || u[v] == 0) return;
	int tm = (tl+tr) >> 1;
	t[v*2] = tm-tl+1-t[v*2];
	t[v*2+1] = tr-tm-t[v*2+1];
	u[v*2+1] ^= u[v];
	u[v*2] ^= u[v];
	u[v] = 0;
}
void updlr(int v, int tl , int tr , int l , int r){
	push(v,tl,tr);
	if(l <= tl && tr <= r){
		t[v] = tr-tl+1-t[v];
		u[v] = 1;
		return;;
	}
	if(tl > r || tr < l) return;
	int tm = (tl+tr) >> 1;
	updlr(v*2,tl,tm,l,r);
	updlr(v*2+1,tm+1,tr,l,r);
	t[v] = t[v*2]+t[v*2+1];
}
int dfs(int v , int pr){
	P[v] = pr;
	D[v] = D[pr]+1;
	int sz = 1;
	int mx = 0;
	sub[v] = 0;
	for(int to : g[v]){
		if(to != pr){
			int tosz = dfs(to,v);
			sz += tosz;
			sub[v] += sub[to];
			if(tosz > mx){
				mx = tosz;
				H[v] = to;
			}
		}
	}
	if(g[v].size() == 1) sub[v] = 1;
	return sz;
}
void decompose(int v, int h){
	B[v] = h;
	pos[v] = ++NW;
	// cout << sub[v] << " "  << v << "\n";
	upd(1,1,n,NW,1-sub[v]%2);
	if(H[v]) decompose(H[v],h);
	for(int to : g[v]){
		if(to != P[v] && to != H[v]) decompose(to,to);
	}
}
void update(int a , int b){
	for(;; b = P[B[b]]){
		// cout << B[b] <<" " << b << "\n";
		updlr(1,1,n,pos[B[b]],pos[b]);
		if(b == a) break;
		if(B[b] == a) break;
	}
}
void solve(){
	cin >> n >> q;
	NW = 0;
	for(int i = 1; i < n; i++){
		cin >> a[i] >> b[i];
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	int kol = 0;
	int st = 1;
	for(int i = 1; i <= n; i++){
		if(g[i].size() != 1){
			st = i;
			break;
		}
	}
	for(int i = 1; i <= n; i++){
		if(g[i].size() == 1) kol++;
	}
	dfs(st,st);
	decompose(st,st);
	while(q--){
		int k;
		cin >> k;
		set<int> stt;
		for(int i = 1; i <= k; i++){
			int a;
			cin >> a;
			cnt[a]++;
			stt.insert(a);
		}
		for(auto x : stt){
			int nw = (cnt[x]-(g[x].size() == 1));
			kol += nw;
			if(nw%2) update(st,x);
		}
		if(kol % 2 == 1) cout << "-1\n";
		else cout << t[1]+n+k-2 << "\n"; 
		for(auto x : stt){ 
			int nw = (cnt[x]-(g[x].size() == 1));
			kol -= nw;
			if(nw%2) update(st,x);
			cnt[x] = 0;
		}
	}	
}
/*

*/
signed main(){
	ios;
	solve();
	return 0;
} 

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30