Submission #1146050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146050		peterandvoi	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	144 ms	29508 KiB

cleaning

// If I remeber correctly, this is an CEOI problem that I had done. Still I barely remeber anything :)
// It's true, vjudge spoiled it : )

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\debug.h"
#else
#define debug(...) 42
#endif

void test();

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  // int tests; cin >> tests; for (int t = 0; t < tests; ++t)
  test();
}

struct st {
  int n;
  vector<int> s, lz, size;
  st(int n = 0): n(n), s(4 * n), lz(4 * n), size(4 * n) {};
  void bld(int id, int l, int r) {
    size[id] = r - l + 1;
    if (l == r) {
      return;
    }
    int m = (l + r) / 2;
    bld(id * 2, l, m);
    bld(id * 2 + 1, m + 1, r);
    s[id] = s[id * 2] + s[id * 2 + 1]; 
  }
  void flip(int u, int v, int id, int l, int r) {
    if (u <= l && r <= v) {
      app(id);
      return;
    }
    psh(id);
    int m = (l + r) / 2;
    if (u <= m) {
      flip(u, v, id * 2, l, m);
    }
    if (m < v) {
      flip(u, v, id * 2 + 1, m + 1, r);
    }
    s[id] = s[id * 2] + s[id * 2 + 1];
  }
  void app(int id) {
    lz[id] ^= 1;
    s[id] = size[id] - s[id];
  }
  void psh(int id) {
    if (lz[id]) {
      app(id * 2);
      app(id * 2 + 1);
      lz[id] ^= 1;
    }
  }
  int count() {
    return s[1];
  }
};

void test() {
  int n, q; cin >> n >> q;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int u, v; cin >> u >> v; --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  vector<int> head(n), pr(n), sz(n), tin(n);
  auto dfs = [&](auto self, int u) -> void {
    sz[u] = 1;
    for (int v : g[u]) {
      g[v].erase(find(g[v].begin(), g[v].end(), u));
      pr[v] = u;
      self(self, v);
      sz[u] += sz[v];
    }
  };
  auto hld = [&](auto self, int u, int h) -> void {
    static int order = 0;
    head[u] = h;
    tin[u] = order++;
    if (g[u].empty()) {
      return;
    }
    int x = *max_element(g[u].begin(), g[u].end(), [&](int a, int b) {
      return sz[a] < sz[b];
    });
    self(self, x, h);
    for (int v : g[u]) {
      if (v ^ x) {
        self(self, v, v);
      }
    }
  };
  int root = 0;
  for (int i = 0; i < n; ++i) {
    if (g[i].size() > 1) {
      root = i;
      break;
    }
  }
  dfs(dfs, root);
  hld(hld, root, root);
  st tree(n);
  tree.bld(1, 0, n - 1);
  auto flip = [&](int u) {
    for (; head[u] ^ root; u = pr[head[u]]) {
      tree.flip(tin[head[u]], tin[u], 1, 0, n - 1);
    }
    tree.flip(0, tin[u], 1, 0, n - 1);
  };
  int leafs = 0;
  auto DFS = [&](auto self, int u) -> bool {
    bool c = 0;
    if (sz[u] == 1) {
      ++leafs;
      c = 1;
    } else for (int v : g[u]) {
      c ^= self(self, v);
    }
    if (c) {
      tree.flip(tin[u], tin[u], 1, 0, n - 1);
    }
    return c;
  };
  DFS(DFS, root);
  while (q--) {
    int D; cin >> D;
    vector<int> add(D);
    map<int, int> cnt;
    int cur_leafs = leafs;
    for (int i = 0; i < D; ++i) {
      int a; cin >> a; --a;
      ++cnt[a];
      ++cur_leafs;
    }
    for (const auto &[x, y] : cnt) {
      cur_leafs -= sz[x] == 1;
      if (y % 2 != (sz[x] == 1)) {
        flip(x);
      }
    }
    if (cur_leafs & 1) {
      cout << -1 << "\n";
    } else {
      int cnt_odd = tree.count();
      cout << D + cnt_odd + (n - 1 - cnt_odd) * 2 << "\n";
    }
    for (const auto &[x, y] : cnt) if (y % 2 != (sz[x] == 1)) {
      flip(x);
    }
  }
}

• 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