oj.uz

Submission #792616

# Submission time Handle Problem Language Result Execution time Memory
792616 2023-07-25T07:27:20 Z ymm Spring cleaning (CEOI20_cleaning) C++17
28 / 100
 1000 ms 20944 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 5812 KB Output is correct

Subtask #2
0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4856 KB Output is correct
2 Correct 32 ms 4928 KB Output is correct
3 Correct 40 ms 20944 KB Output is correct
4 Correct 100 ms 20684 KB Output is correct
5 Correct 35 ms 18152 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 11672 KB Output is correct
2 Correct 69 ms 11596 KB Output is correct
3 Correct 56 ms 7420 KB Output is correct
4 Correct 73 ms 11584 KB Output is correct
5 Correct 69 ms 11576 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 16728 KB Output is correct
2 Execution timed out 1078 ms 18108 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 5812 KB Output is correct
3 Incorrect 10 ms 4180 KB Output isn't correct
4 Halted 0 ms 0 KB -