Submission #754432

#	Time	Username	Problem	Language	Result	Execution time	Memory
754432		NintsiChkhaidze	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	384 ms	21444 KiB

cleaning

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l + r)>>1) + 1,r
#define pii pair <int,int>
using namespace std;

const int N = 2e5 + 5;

vector <int> v[N];
int head[N],heavy[N],timer,tin[N],lz[4*N];
int parent[N],t[4*N],n,fix[N],sub[N],root;
vector <pii> vec;

void push(int h,int l,int r){
	if (!lz[h]) return;
	lz[h*2] ^= 1;
	lz[h*2+1]^=1;
	int mid=(l+r)/2;
	t[h*2]=(mid - l + 1) - t[h*2];
	t[h*2+1] = (r - mid) - t[h*2 + 1];
	lz[h]=0;
}
void upd(int h,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		lz[h] ^= 1;
		t[h] = (r - l + 1) - t[h];
		return;
	}
	push(h,l,r);
	upd(left,L,R);
	upd(right,L,R);
	t[h] = t[h*2] + t[h*2 + 1];
}

void dfs(int x){
	sub[x] = 1;

	for (int to: v[x]){
		if (to == parent[x]) continue;

		parent[to] = x;
		dfs(to);
		sub[x] += sub[to];
		
		if (sub[to] > sub[heavy[x]]) heavy[x] = to;
	}

}

void dfs2(int x,int hh){
	head[x] = hh;
	tin[x] = ++timer;
	if (heavy[x]) dfs2(heavy[x],hh);

	for (int to: v[x]){
		if (to==parent[x] || to == heavy[x]) continue;
		dfs2(to,to);
	}
}

void update(int x){
	while (x != root){
		upd(1,1,n,tin[head[x]],tin[x]);
		if (head[x] == root) return;
		x = parent[head[x]];
	}
	upd(1,1,n,1,1);
}

int main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int m;
	cin>>n>>m;
	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	// for (int i= 1; i <= n; i++){
	// 	if (v[i].size() > 1) {root = i; break;}
	// }

	root = 1;
	dfs(root);
	dfs2(root,root);

	int LL=0;
	for (int i = 1; i <= n; i++){
		if (v[i].size() == 1) update(i),LL++;
	}

	for (int j = 1; j <= m; j++){
		int x;
		cin>>x;
		int L=LL;

		vector <int> vert;
		for (int i = 1; i <= x; i++){
			int nd;
			cin>>nd;

			if (!fix[nd] && v[nd].size() == 1){
				--L;
				fix[nd] = 1;
			}
			else {
				update(nd);
				
			}
			vert.pb(nd);
		}
		L += x;

		if (!(L%2))
			cout<<2*n + x - 2 - t[1]<<endl;
		else 
			cout<<-1<<endl;

		for (int y: vert) fix[y]=0;
		for (int nd: vert){
			if (!fix[nd] && v[nd].size() == 1){
				--L;
				fix[nd] = 1;
			}
			else {
				update(nd);
			}
		}
		for (int y: vert) fix[y]=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