oj.uz

Submission #658651

# Submission time Handle Problem Language Result Execution time Memory
658651 2022-11-14T05:08:39 Z lunchbox1 Spring cleaning (CEOI20_cleaning) C++17
28 / 100
 1000 ms 13036 KB 
/*
 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 (x > t)
    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 302 ms 4428 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3284 KB Output is correct
2 Correct 13 ms 3292 KB Output is correct
3 Correct 75 ms 10516 KB Output is correct
4 Correct 73 ms 9612 KB Output is correct
5 Correct 108 ms 11112 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 7312 KB Output is correct
2 Correct 364 ms 7184 KB Output is correct
3 Correct 240 ms 4916 KB Output is correct
4 Correct 339 ms 7096 KB Output is correct
5 Correct 346 ms 7116 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 10712 KB Output is correct
2 Execution timed out 1091 ms 13036 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 302 ms 4428 KB Output is correct
3 Correct 13 ms 3284 KB Output is correct
4 Correct 13 ms 3292 KB Output is correct
5 Correct 75 ms 10516 KB Output is correct
6 Correct 73 ms 9612 KB Output is correct
7 Correct 108 ms 11112 KB Output is correct
8 Execution timed out 1077 ms 3940 KB Time limit exceeded
9 Halted 0 ms 0 KB -