Submission #658652

#	Time	Username	Problem	Language	Result	Execution time	Memory
658652		lunchbox1	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	266 ms	19228 KiB

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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30