oj.uz

Submission #792650

# Submission time Handle Problem Language Result Execution time Memory
792650 2023-07-25T07:51:19 Z ymm Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 19460 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 {
	ll *t;
	int l;
	void init(int b, int e) {
		l = b;
		t = new ll[(e-b+63)/64]{};
	}
	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 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3792 KB Output is correct
2 Correct 12 ms 3768 KB Output is correct
3 Correct 31 ms 13612 KB Output is correct
4 Correct 66 ms 10888 KB Output is correct
5 Correct 65 ms 14008 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4436 KB Output is correct
2 Correct 26 ms 4488 KB Output is correct
3 Correct 43 ms 19460 KB Output is correct
4 Correct 342 ms 18500 KB Output is correct
5 Correct 50 ms 17888 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 5352 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 8772 KB Output is correct
2 Correct 53 ms 8728 KB Output is correct
3 Correct 40 ms 5784 KB Output is correct
4 Correct 75 ms 8652 KB Output is correct
5 Correct 69 ms 8816 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12476 KB Output is correct
2 Execution timed out 1085 ms 14940 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 2644 KB Output is correct
2 Correct 36 ms 4624 KB Output is correct
3 Correct 12 ms 3792 KB Output is correct
4 Correct 12 ms 3768 KB Output is correct
5 Correct 31 ms 13612 KB Output is correct
6 Correct 66 ms 10888 KB Output is correct
7 Correct 65 ms 14008 KB Output is correct
8 Correct 25 ms 4436 KB Output is correct
9 Correct 26 ms 4488 KB Output is correct
10 Correct 43 ms 19460 KB Output is correct
11 Correct 342 ms 18500 KB Output is correct
12 Correct 50 ms 17888 KB Output is correct
13 Execution timed out 1083 ms 5352 KB Time limit exceeded
14 Halted 0 ms 0 KB -