Submission #658652

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658652	2022-11-14T05:09:11 Z	lunchbox1	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	266 ms	19228 KB

cleaning

/*
 Spring Cleaning
 https://oj.uz/problem/view/CEOI20_cleaning
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

vector<int> g[N];
int p[N], c[N], z[N], o[N];

int dfs1(int i) {
 int s = 1, x = 0;
 c[i] = -1;
 for (int j : g[i])
  if (p[i] != j) {
   p[j] = i;
   int t = dfs1(j);
   if (t > x)
    x = t, c[i] = j;
   s += t;
  }
 return s;
}

void dfs2(int r, int i) {
 static int t = 0;
 o[i] = t++;
 z[i] = r;
 if (c[i] != -1)
  dfs2(r, c[i]);
 for (int j : g[i])
  if (p[i] != j && c[i] != j)
   dfs2(j, j);
}

int t0[N * 4], t1[N * 4], lz[N * 4];

void build(int k, int l, int r) {
 t0[k] = r - l + 1;
 if (l != r) {
  int m = (l + r) / 2;
  build(k << 1 | 0, l, m), build(k << 1 | 1, m + 1, r);
 }
}

void put(int k) {
 swap(t0[k], t1[k]);
 lz[k] ^= 1;
}

void update(int k, int l, int r, int ql, int qr) {
 if (ql > r || qr < l)
  return;
 else if (ql <= l && qr >= r)
  put(k);
 else {
  int m = (l + r) / 2;
  if (lz[k])
   put(k << 1 | 0), put(k << 1 | 1), lz[k] = 0;
  update(k << 1 | 0, l, m, ql, qr), update(k << 1 | 1, m + 1, r, ql, qr);
  t0[k] = t0[k << 1 | 0] + t0[k << 1 | 1], t1[k] = t1[k << 1 | 0] + t1[k << 1 | 1];
 }
}

int n;

void update(int i) {
 while (i != -1) {
  update(1, 0, n - 1, o[z[i]], o[i]);
  i = p[z[i]];
 }
}

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int q;
 cin >> n >> q;
 for (int h = 0; h < n - 1; h++) {
  int i, j;
  cin >> i >> j, i--, j--;
  g[i].push_back(j), g[j].push_back(i);
 }
 int r = 0;
 while (g[r].size() == 1)
  r++;
 p[r] = -1;
 dfs1(r);
 dfs2(r, r);
 int l = 0;
 build(1, 0, n - 1);
 for (int i = 0; i < n; i++)
  if (g[i].size() == 1)
   update(i), l++;
 while (q--) {
  int d;
  cin >> d;
  vector<int> t(d), u;
  for (int& i : t)
   cin >> i, i--;
  sort(t.begin(), t.end());
  int l_ = l + d;
  for (int i = 0, j; i < (int) t.size(); i = j) {
   j = i;
   while (j < (int) t.size() && t[i] == t[j])
    j++;
   if ((g[t[i]].size() > 1) ^ ((j - i) % 2 == 0))
    update(t[i]), u.push_back(t[i]);
   l_ -= g[t[i]].size() == 1;
  }
  cout << (l_ % 2 == 1 ? -1 : n + d + t0[1] - 2) << '\n';
  for (int i : u)
   update(i);
 }
 return 0;
}

Subtask #1

0.0 / 0.0

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

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	3292 KB	Output is correct
2	Correct	14 ms	3284 KB	Output is correct
3	Correct	72 ms	10600 KB	Output is correct
4	Correct	77 ms	9616 KB	Output is correct
5	Correct	92 ms	11044 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	3796 KB	Output is correct
2	Correct	14 ms	4188 KB	Output is correct
3	Correct	44 ms	19192 KB	Output is correct
4	Correct	69 ms	19228 KB	Output is correct
5	Correct	50 ms	17072 KB	Output is correct

Subtask #4

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	5392 KB	Output is correct
2	Correct	39 ms	4812 KB	Output is correct
3	Correct	18 ms	4652 KB	Output is correct
4	Correct	13 ms	5128 KB	Output is correct
5	Correct	16 ms	5376 KB	Output is correct
6	Correct	51 ms	5432 KB	Output is correct

Subtask #5

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	7540 KB	Output is correct
2	Correct	266 ms	7404 KB	Output is correct
3	Correct	169 ms	5020 KB	Output is correct
4	Correct	249 ms	7372 KB	Output is correct
5	Correct	218 ms	7372 KB	Output is correct

Subtask #6

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	216 ms	10956 KB	Output is correct
2	Correct	135 ms	14176 KB	Output is correct
3	Correct	162 ms	15692 KB	Output is correct
4	Correct	207 ms	15076 KB	Output is correct

Subtask #7

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	85 ms	4460 KB	Output is correct
3	Correct	15 ms	3292 KB	Output is correct
4	Correct	14 ms	3284 KB	Output is correct
5	Correct	72 ms	10600 KB	Output is correct
6	Correct	77 ms	9616 KB	Output is correct
7	Correct	92 ms	11044 KB	Output is correct
8	Correct	18 ms	3796 KB	Output is correct
9	Correct	14 ms	4188 KB	Output is correct
10	Correct	44 ms	19192 KB	Output is correct
11	Correct	69 ms	19228 KB	Output is correct
12	Correct	50 ms	17072 KB	Output is correct
13	Correct	48 ms	5392 KB	Output is correct
14	Correct	39 ms	4812 KB	Output is correct
15	Correct	18 ms	4652 KB	Output is correct
16	Correct	13 ms	5128 KB	Output is correct
17	Correct	16 ms	5376 KB	Output is correct
18	Correct	51 ms	5432 KB	Output is correct
19	Correct	203 ms	7540 KB	Output is correct
20	Correct	266 ms	7404 KB	Output is correct
21	Correct	169 ms	5020 KB	Output is correct
22	Correct	249 ms	7372 KB	Output is correct
23	Correct	218 ms	7372 KB	Output is correct
24	Correct	216 ms	10956 KB	Output is correct
25	Correct	135 ms	14176 KB	Output is correct
26	Correct	162 ms	15692 KB	Output is correct
27	Correct	207 ms	15076 KB	Output is correct
28	Correct	179 ms	8420 KB	Output is correct
29	Correct	138 ms	15292 KB	Output is correct
30	Correct	109 ms	12384 KB	Output is correct
31	Correct	64 ms	19116 KB	Output is correct
32	Correct	250 ms	8576 KB	Output is correct
33	Correct	149 ms	13516 KB	Output is correct
34	Correct	174 ms	15376 KB	Output is correct
35	Correct	156 ms	15308 KB	Output is correct