oj.uz

Submission #293180

# Submission time Handle Problem Language Result Execution time Memory
293180 2020-09-07T17:38:59 Z luciocf Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 884 ms 20484 KB 
// CEOI 2020 - Spring Cleaning
// Lúcio Cardoso

// Solution is the same as in editorial (with HLD)

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n, q;

vector<int> grafo[maxn];

struct SegmentTree
{
	int tree[2][4*maxn], lazy[4*maxn];

	void build(int node, int l, int r)
	{
		tree[0][node] = r-l+1;
		if (l == r) return;

		int mid = (l+r)>>1;

		build(2*node, l, mid); build(2*node+1, mid+1, r);
	}

	void flush(int node, int l, int r)
	{
		if (!lazy[node]) return;

		if (l != r) lazy[2*node] += lazy[node], lazy[2*node+1] += lazy[node];

		if (abs(lazy[node])%2) swap(tree[0][node], tree[1][node]);

		lazy[node] = 0;
	}

	void upd(int node, int l, int r, int a, int b, int v)
	{
		flush(node, l, r);
		if (l > b || r < a) return;

		if (l >= a && r <= b)
		{
			lazy[node] = v;
			flush(node, l, r);
			return;
		}

		int mid = (l+r)>>1;

		upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

		tree[0][node] = tree[0][2*node]+tree[0][2*node+1];
		tree[1][node] = tree[1][2*node]+tree[1][2*node+1];
	}
} seg;

struct HeavyLight
{
	int pai[maxn], nivel[maxn], sub[maxn];
	int head[maxn], chain[maxn], pos[maxn], cc, tt;

	void init(void)
	{
		cc = 1;
	}

	void dfs(int u, int p)
	{
		sub[u] = 1;
		for (auto v: grafo[u])
		{
			if (v == p) continue;

			pai[v] = u, nivel[v] = nivel[u]+1;
			dfs(v, u);
			sub[u] += sub[v];
		}
	}

	void hld(int u)
	{
		if (!head[cc]) head[cc] = u;
		chain[u] = cc, pos[u] = ++tt;

		int mx = 0, ind = -1;
		for (auto v: grafo[u])
			if (v != pai[u] && sub[v] > mx)
				mx = sub[v], ind = v;

		if (ind != -1) hld(ind);

		for (auto v: grafo[u])
		{
			if (v != pai[u] && v != ind)
			{
				++cc;
				hld(v);
			}
		}
	}

	void upd_path(int u, int v, int k)
	{
		while (true)
		{
			if (chain[u] == chain[v])
			{
				seg.upd(1, 1, n, pos[v], pos[u], k);
				return;
			}

			seg.upd(1, 1, n, pos[head[chain[u]]], pos[u], k);
			u = pai[head[chain[u]]];
		}
	}
} HLD;

int liga[maxn];

int main(void)
{
	scanf("%d %d", &n, &q);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	int r;
	for (int i = 1; i <= n; i++)
		if (grafo[i].size() != 1)
			r = i;


	seg.build(1, 1, n);
	HLD.init(); HLD.dfs(r, 0); HLD.hld(r);

	for (int i = 1; i <= n; i++)
		if (grafo[i].size() == 1)
			HLD.upd_path(i, r, 1);


	int leaf = 0;
	for (int i = 1; i <= n; i++)
		if (grafo[i].size() == 1)
			leaf++;

	while (q--)
	{
		int d;
		scanf("%d", &d);

		int l = leaf+d;

		vector<int> A;
		set<int> B;

		for (int i = 1; i <= d; i++)
		{
			int u;
			scanf("%d", &u);

			liga[d] = u;

			HLD.upd_path(u, r, 1);

			A.push_back(u);
			B.insert(u);
		}

		for (auto v: B)
		{
			if (grafo[v].size() == 1)
			{
				l--;
				HLD.upd_path(v, r, -1);
			}
		}

		int ans = n+d-1;
		seg.flush(1, 1, n);
		ans += seg.tree[0][1]-1;

		if (l%2) printf("-1\n");
		else printf("%d\n", ans);

		for (auto v: B)
			if (grafo[v].size() == 1)
				HLD.upd_path(v, r, 1);

		for (auto v: A)
			HLD.upd_path(v, r, -1);
	}
}

Compilation message

cleaning.cpp: In function 'int main()':
cleaning.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
cleaning.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
cleaning.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~
cleaning.cpp:170:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  170 |    scanf("%d", &u);
      |    ~~~~~^~~~~~~~~~
cleaning.cpp:113:12: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     seg.upd(1, 1, n, pos[v], pos[u], k);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cleaning.cpp:138:6: note: 'r' was declared here
  138 |  int r;
      |      ^

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 383 ms 4836 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3768 KB Output is correct
2 Correct 87 ms 3804 KB Output is correct
3 Correct 127 ms 11628 KB Output is correct
4 Correct 325 ms 12392 KB Output is correct
5 Correct 394 ms 14584 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 4524 KB Output is correct
2 Correct 83 ms 4468 KB Output is correct
3 Correct 79 ms 18680 KB Output is correct
4 Correct 235 ms 20484 KB Output is correct
5 Correct 67 ms 16504 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 5100 KB Output is correct
2 Correct 141 ms 4728 KB Output is correct
3 Correct 31 ms 4608 KB Output is correct
4 Correct 20 ms 4992 KB Output is correct
5 Correct 29 ms 4984 KB Output is correct
6 Correct 136 ms 5240 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 8184 KB Output is correct
2 Correct 884 ms 7980 KB Output is correct
3 Correct 692 ms 5568 KB Output is correct
4 Correct 853 ms 7896 KB Output is correct
5 Correct 855 ms 8008 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 771 ms 11784 KB Output is correct
2 Correct 368 ms 14584 KB Output is correct
3 Correct 403 ms 13688 KB Output is correct
4 Correct 386 ms 14272 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 383 ms 4836 KB Output is correct
3 Correct 87 ms 3768 KB Output is correct
4 Correct 87 ms 3804 KB Output is correct
5 Correct 127 ms 11628 KB Output is correct
6 Correct 325 ms 12392 KB Output is correct
7 Correct 394 ms 14584 KB Output is correct
8 Correct 85 ms 4524 KB Output is correct
9 Correct 83 ms 4468 KB Output is correct
10 Correct 79 ms 18680 KB Output is correct
11 Correct 235 ms 20484 KB Output is correct
12 Correct 67 ms 16504 KB Output is correct
13 Correct 219 ms 5100 KB Output is correct
14 Correct 141 ms 4728 KB Output is correct
15 Correct 31 ms 4608 KB Output is correct
16 Correct 20 ms 4992 KB Output is correct
17 Correct 29 ms 4984 KB Output is correct
18 Correct 136 ms 5240 KB Output is correct
19 Correct 546 ms 8184 KB Output is correct
20 Correct 884 ms 7980 KB Output is correct
21 Correct 692 ms 5568 KB Output is correct
22 Correct 853 ms 7896 KB Output is correct
23 Correct 855 ms 8008 KB Output is correct
24 Correct 771 ms 11784 KB Output is correct
25 Correct 368 ms 14584 KB Output is correct
26 Correct 403 ms 13688 KB Output is correct
27 Correct 386 ms 14272 KB Output is correct
28 Correct 645 ms 7948 KB Output is correct
29 Correct 412 ms 13560 KB Output is correct
30 Correct 408 ms 14528 KB Output is correct
31 Correct 243 ms 20464 KB Output is correct
32 Correct 866 ms 8104 KB Output is correct
33 Correct 380 ms 13348 KB Output is correct
34 Correct 479 ms 13388 KB Output is correct
35 Correct 445 ms 14448 KB Output is correct