Submission #792653

#	Time	Username	Problem	Language	Result	Execution time	Memory
792653		ymm	Spring cleaning (CEOI20_cleaning)	C++17	37 / 100	1093 ms	19276 KiB

cleaning

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 100'010;
vector<int> A[N];
int rt;
int cnt[N];
int height[N];
int par[N];

struct seg {
	ll *t;
	int l;
	void init(int b, int e) {
		l = b;
		t = new ll[(e-b+63)/64]{};
	}
	__attribute__((optimize("O3,unroll-loops"),target("avx2,popcnt,abm,bmi,bmi2")))
	int up(int r) {
		r = r+1-l;
		int ans = 0;
		Loop (i,0,r/64) {
			ll x = t[i];
			x = ~x;
			ans += 2*__builtin_popcountll(x) - 64;
			t[i] = x;
		}
		if (r%64) {
			ll x = t[r/64];
			ans -= __builtin_popcountll(x);
			x ^= (1ll<<(r%64))-1;
			ans += __builtin_popcountll(x);
			t[r/64] = x;
		}
		return ans;
	}
	//struct node {
	//	int cnt;
	//	bool rev;
	//};
	//node *t;
	//int l, r;

	//void init(int b, int e) {
	//	l = b;
	//	r = e;
	//	t = new node[(r-l)*4]{};
	//}

	//void merge(int i, int b, int e) {
	//	t[i].cnt = t[2*i+1].cnt + t[2*i+2].cnt;
	//	t[i].cnt = t[i].rev? e-b-t[i].cnt: t[i].cnt;
	//}

	//void up(int l, int r, int i, int b, int e) {
	//	if (l <= b && e <= r) {
	//		t[i].cnt = e-b-t[i].cnt;
	//		t[i].rev = !t[i].rev;
	//		return;
	//	}
	//	if (l < (b+e)/2)
	//		up(l, r, 2*i+1, b, (b+e)/2);
	//	if ((b+e)/2 < r)
	//		up(l, r, 2*i+2, (b+e)/2, e);
	//	merge(i, b, e);
	//}
	//int up(int lst) {
	//	int tmp = t[0].cnt;
	//	up(l, lst+1, 0, l, r);
	//	return t[0].cnt - tmp;
	//}
};

struct {
	int rt;
	int sz;
	int ch;
	seg sg;
} hv[N];

void dfs0(int v, int p)
{
	cnt[v] = 0;
	hv[v].ch = -1;
	for (int u : A[v]) {
		if (u == p)
			continue;
		dfs0(u, v);
		cnt[v] += cnt[u];
		if (hv[v].ch == -1 || cnt[u] > cnt[hv[v].ch])
			hv[v].ch = u;
	}
}

int Ans = 0;
int cntlf = 0;

void dfs1(int v, int p, int rt, int h)
{
	par[v] = p;
	height[v] = h;
	hv[v].rt = rt;
	hv[rt].sz++;
	for (int u : A[v]) {
		if (u == p)
			continue;
		dfs1(u, v, u == hv[v].ch? rt: u, h+1);
	}
	if (hv[v].rt == v) {
		hv[v].sg.init(height[v], height[v] + hv[v].sz);
		Ans += hv[v].sg.up(height[v] + hv[v].sz - 1);
	}
}

void up(int v)
{
	while (v != -1) {
		int rt = hv[v].rt;
		Ans += hv[rt].sg.up(height[v]);
		v = par[rt];
	}
}

void add(int v)
{
	A[v].push_back(-1);
	if (A[v].size() == 2)
		return;
	++cntlf;
	up(v);
}
void rem(int v)
{
	A[v].pop_back();
	if (A[v].size() == 1)
		return;
	--cntlf;
	up(v);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs0(0, -1);
	dfs1(0, -1, 0, 0);
	Loop (i,0,n) {
		if (A[i].size() != 1)
			continue;
		up(i);
		cntlf += 1;
	}
	while (q--) {
		int k;
		cin >> k;
		vector<int> a(k);
		for (int &v : a) {
			cin >> v;
			--v;
		}
		for (int v : a)
			add(v);
		if (cntlf%2 == 1)
			cout << "-1\n";
		else
			cout << Ans-1 + n-1 + k << '\n';
		for (int v : a)
			rem(v);
	}
}

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