oj.uz

Submission #792620

# Submission time Handle Problem Language Result Execution time Memory
792620 2023-07-25T07:30:10 Z ymm Spring cleaning (CEOI20_cleaning) C++17
37 / 100
 1000 ms 20820 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 {
	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 37 ms 5000 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3776 KB Output is correct
2 Correct 10 ms 4236 KB Output is correct
3 Correct 29 ms 15940 KB Output is correct
4 Correct 33 ms 12964 KB Output is correct
5 Correct 45 ms 16884 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4436 KB Output is correct
2 Correct 30 ms 4452 KB Output is correct
3 Correct 36 ms 20820 KB Output is correct
4 Correct 100 ms 19844 KB Output is correct
5 Correct 32 ms 19132 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 10404 KB Output is correct
2 Correct 72 ms 10188 KB Output is correct
3 Correct 45 ms 6504 KB Output is correct
4 Correct 71 ms 10272 KB Output is correct
5 Correct 65 ms 10292 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 14808 KB Output is correct
2 Execution timed out 1080 ms 16716 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 37 ms 5000 KB Output is correct
3 Correct 10 ms 3776 KB Output is correct
4 Correct 10 ms 4236 KB Output is correct
5 Correct 29 ms 15940 KB Output is correct
6 Correct 33 ms 12964 KB Output is correct
7 Correct 45 ms 16884 KB Output is correct
8 Correct 31 ms 4436 KB Output is correct
9 Correct 30 ms 4452 KB Output is correct
10 Correct 36 ms 20820 KB Output is correct
11 Correct 100 ms 19844 KB Output is correct
12 Correct 32 ms 19132 KB Output is correct
13 Execution timed out 1064 ms 5680 KB Time limit exceeded
14 Halted 0 ms 0 KB -