oj.uz

Submission #792643

# Submission time Handle Problem Language Result Execution time Memory
792643 2023-07-25T07:46:57 Z ymm Spring cleaning (CEOI20_cleaning) C++17
28 / 100
 1000 ms 15300 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 ^= (1<<(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 35 ms 4604 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3796 KB Output is correct
2 Correct 12 ms 4180 KB Output is correct
3 Correct 43 ms 14436 KB Output is correct
4 Correct 40 ms 11844 KB Output is correct
5 Correct 56 ms 15300 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 4400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 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 51 ms 8808 KB Output is correct
2 Correct 75 ms 8868 KB Output is correct
3 Correct 36 ms 5860 KB Output is correct
4 Correct 57 ms 8804 KB Output is correct
5 Correct 53 ms 8800 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 12548 KB Output is correct
2 Execution timed out 1083 ms 15052 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 35 ms 4604 KB Output is correct
3 Correct 12 ms 3796 KB Output is correct
4 Correct 12 ms 4180 KB Output is correct
5 Correct 43 ms 14436 KB Output is correct
6 Correct 40 ms 11844 KB Output is correct
7 Correct 56 ms 15300 KB Output is correct
8 Incorrect 25 ms 4400 KB Output isn't correct
9 Halted 0 ms 0 KB -