oj.uz

Submission #792720

# Submission time Handle Problem Language Result Execution time Memory
792720 2023-07-25T08:15:48 Z ymm Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 25316 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 ymm __attribute__((aligned(32),vector_size(32)));
	ymm *yt;
	ll *t;
	int l, r;
	void init(int b, int e) {
		l = b;
		r = e;
		yt = new ymm[(e-b+255)/256]{};
		t = (ll *)(void *)yt;
	}
	__attribute__((optimize("O3,unroll-loops"),target("avx2,popcnt")))
	int up(int r) {
		r = r+1-l;
		int ans = 0;
		ymm yans = {};
		Loop (i,0,r/256) {
			ymm x = yt[i];
			x = ~x;
			ymm z = x;
			//unsigned short s1 = 0b10101010'10101010;
			//unsigned short s2 = 0b00110011'00110011;
			//unsigned short s3 = 0b00001111'00001111;
			//unsigned short s4 = 0b00000000'11111111;
			//z -= (z & s1) >> 1;
			//z = (z & s2) + ((z >> 2) & s2);
			//z = (z & s3) + ((z >> 4) & s3);
			//z = (z & s4) + ((z >> 8) & s4);
			z -= (z & (unsigned short)0b10101010'10101010) >> 1;
			z = (z & 0b00110011'00110011) + ((z >> 2) & 0b00110011'00110011);
			z = (z + (z >> 4)) & 0b00001111'00001111;
			z = (z + (z >> 8)) & 0b00000000'11111111;
			yans += z;
			yt[i] = x;
		}
		ans -= r - r%256;
		Loop (i,0,16)
			ans += 2*yans[i];
		Loop (i,r/256*4,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 1 ms 2684 KB Output is correct
2 Correct 36 ms 6356 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4436 KB Output is correct
2 Correct 11 ms 4436 KB Output is correct
3 Correct 59 ms 24608 KB Output is correct
4 Correct 57 ms 18840 KB Output is correct
5 Correct 67 ms 25316 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4820 KB Output is correct
2 Correct 17 ms 4820 KB Output is correct
3 Correct 41 ms 21228 KB Output is correct
4 Correct 106 ms 20696 KB Output is correct
5 Correct 44 ms 19504 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13652 KB Output is correct
2 Correct 57 ms 13536 KB Output is correct
3 Correct 35 ms 8392 KB Output is correct
4 Correct 73 ms 13536 KB Output is correct
5 Correct 70 ms 13576 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 19624 KB Output is correct
2 Execution timed out 1080 ms 21792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2684 KB Output is correct
2 Correct 36 ms 6356 KB Output is correct
3 Correct 13 ms 4436 KB Output is correct
4 Correct 11 ms 4436 KB Output is correct
5 Correct 59 ms 24608 KB Output is correct
6 Correct 57 ms 18840 KB Output is correct
7 Correct 67 ms 25316 KB Output is correct
8 Correct 21 ms 4820 KB Output is correct
9 Correct 17 ms 4820 KB Output is correct
10 Correct 41 ms 21228 KB Output is correct
11 Correct 106 ms 20696 KB Output is correct
12 Correct 44 ms 19504 KB Output is correct
13 Execution timed out 1080 ms 6816 KB Time limit exceeded
14 Halted 0 ms 0 KB -