oj.uz

Submission #792653

# Submission time Handle Problem Language Result Execution time Memory
792653 2023-07-25T07:52:36 Z ymm Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 19276 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]{};
	}
	__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 / 0.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3796 KB Output is correct
2 Correct 16 ms 3856 KB Output is correct
3 Correct 38 ms 13640 KB Output is correct
4 Correct 45 ms 10748 KB Output is correct
5 Correct 42 ms 13984 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4436 KB Output is correct
2 Correct 16 ms 4360 KB Output is correct
3 Correct 42 ms 19276 KB Output is correct
4 Correct 176 ms 18440 KB Output is correct
5 Correct 29 ms 17748 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8748 KB Output is correct
2 Correct 54 ms 8848 KB Output is correct
3 Correct 33 ms 5708 KB Output is correct
4 Correct 46 ms 8736 KB Output is correct
5 Correct 74 ms 8696 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 12540 KB Output is correct
2 Execution timed out 1093 ms 14928 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 29 ms 4636 KB Output is correct
3 Correct 9 ms 3796 KB Output is correct
4 Correct 16 ms 3856 KB Output is correct
5 Correct 38 ms 13640 KB Output is correct
6 Correct 45 ms 10748 KB Output is correct
7 Correct 42 ms 13984 KB Output is correct
8 Correct 23 ms 4436 KB Output is correct
9 Correct 16 ms 4360 KB Output is correct
10 Correct 42 ms 19276 KB Output is correct
11 Correct 176 ms 18440 KB Output is correct
12 Correct 29 ms 17748 KB Output is correct
13 Execution timed out 1079 ms 5348 KB Time limit exceeded
14 Halted 0 ms 0 KB -