oj.uz

Submission #792757

# Submission time Handle Problem Language Result Execution time Memory
792757 2023-07-25T08:31:20 Z ymm Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 20052 KB 
#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 {
	typedef unsigned short xmm __attribute__((aligned(16),vector_size(16)));
	typedef unsigned char xmmc __attribute__((aligned(16),vector_size(16)));
	static xmmc constexpr table = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
	xmm *xt;
	ll *t;
	int l, r;
	void init(int b, int e) {
		l = b;
		r = e;
		xt = new xmm[(e-b+127)/128]{};
		t = (ll *)(void *)xt;
	}
	__attribute__((optimize("O3,unroll-loops"),target("avx2,popcnt")))
	int up(int r) {
		r = r+1-l;
		int ans = 0;
		xmm xans = {};
		Loop (i,0,r/128) {
			xmm x = xt[i];
			x = ~x;
			xmmc zc = reinterpret_cast<xmmc>(x);
			zc = __builtin_shuffle(table, zc) + __builtin_shuffle(table, zc >> 4);
			xmm z = reinterpret_cast<xmm>(zc);
			xans += (z + (z>>8)) & 255;
			xt[i] = x;
		}
		ans -= r - r%128;
		Loop (i,0,8)
			ans += 2*xans[i];
		Loop (i,r/128*2,r/64) {
		//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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 32 ms 4796 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3796 KB Output is correct
2 Correct 10 ms 3796 KB Output is correct
3 Correct 31 ms 14376 KB Output is correct
4 Correct 33 ms 11376 KB Output is correct
5 Correct 44 ms 14764 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 4376 KB Output is correct
2 Correct 19 ms 4436 KB Output is correct
3 Correct 49 ms 20052 KB Output is correct
4 Correct 172 ms 19156 KB Output is correct
5 Correct 30 ms 18492 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 5504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9372 KB Output is correct
2 Correct 49 ms 9144 KB Output is correct
3 Correct 42 ms 6044 KB Output is correct
4 Correct 50 ms 9244 KB Output is correct
5 Correct 50 ms 9156 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13288 KB Output is correct
2 Execution timed out 1091 ms 15796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 32 ms 4796 KB Output is correct
3 Correct 10 ms 3796 KB Output is correct
4 Correct 10 ms 3796 KB Output is correct
5 Correct 31 ms 14376 KB Output is correct
6 Correct 33 ms 11376 KB Output is correct
7 Correct 44 ms 14764 KB Output is correct
8 Correct 19 ms 4376 KB Output is correct
9 Correct 19 ms 4436 KB Output is correct
10 Correct 49 ms 20052 KB Output is correct
11 Correct 172 ms 19156 KB Output is correct
12 Correct 30 ms 18492 KB Output is correct
13 Execution timed out 1084 ms 5504 KB Time limit exceeded
14 Halted 0 ms 0 KB -