Submission #1146159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146159		fryingduc	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	397 ms	21128 KiB

cleaning

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int LG = 19;
int n, q;
int root;
bool is_leaf[maxn];
int eu[maxn], ev[maxn];
vector<int> g[maxn];
int leaves;
int sz[maxn], h[maxn], par[maxn];
int pos[maxn], rev[maxn], head[maxn], cur_pos;

void pre_dfs(int u, int prev) {
  if ((int)g[u].size() == 1) {
    ++leaves;
    is_leaf[u] = 1;
  }
  sz[u] = 1;
  for (auto v : g[u]) {
    if (v == prev) continue;
    par[v] = u;
    h[v] = h[u] + 1;
    pre_dfs(v, u);
    sz[u] += sz[v];
  }
}

void hld(int u, int prev) {
  if (!head[u]) head[u] = u;
  pos[u] = ++cur_pos;
  rev[cur_pos] = u;
  int big_child = -1;
  for (auto v : g[u]) {
    if (v == prev) continue;
    if (big_child == -1 || sz[big_child] < sz[v]) {
      big_child = v;
    }
  }
  if (big_child != -1) {
    head[big_child] = head[u];
    hld(big_child, u);
  }
  for (auto v : g[u]) {
    if (v == prev || v == big_child) continue;
    hld(v, u);
  }
}

int tree[maxn << 2], lazy[maxn << 2];
void build(int ind = 1, int l = 1, int r = n) {
  if (l == r) {
    tree[ind] = (l > 1);
    return;
  }
  int mid = (l + r) >> 1;
  build(ind << 1, l, mid);
  build(ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

void down(int ind, int l, int r) {
  tree[ind] = (r - l + 1) - tree[ind];
  if (l != r) {
    lazy[ind << 1] ^= lazy[ind];
    lazy[ind << 1 | 1] ^= lazy[ind];
  }
  lazy[ind] = 0;
}

void update(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) {
    down(ind, l, r);
  }
  if (l > r || l > y || r < x) return;
  if (x <= l and r <= y) {
    lazy[ind] = 1;
    down(ind, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update(x, y, ind << 1, l, mid);
  update(x, y, ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

int get(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (l > y || r < x) return 0;
  if (x <= l and r <= y) {
    return tree[ind];
  }
  int mid = (l + r) >> 1;
  return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
}

void update(int u) {
  while (head[u] != root) {
    update(pos[head[u]], pos[u]);
    u = par[head[u]];
  }
  update(2, pos[u]);
}

void solve() {
  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    eu[i] = u, ev[i] = v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  root = 1;
  for (int i = 1; i <= n; ++i) {
    if ((int)g[i].size() > 1) {
      root = i;
      break;
    }
  }
  pre_dfs(root, 0);
  h[root] = 1, par[root] = root;
  hld(root, 0);
  build();
  for (int i = 1; i <= n; ++i) {
    if (is_leaf[i]) {
      update(i);
    }
  }
  
  while(q--) {
    int sz; cin >> sz;
    vector<int> cur;
    vector<int> prev_leaf;
    for (int i = 0; i < sz; ++i) {
      int p; cin >> p;
      if (is_leaf[p]) {
        prev_leaf.push_back(p);
      }
      cur.push_back(p);
      update(p);
    }
    sort(prev_leaf.begin(), prev_leaf.end());
    prev_leaf.erase(unique(prev_leaf.begin(), prev_leaf.end()), prev_leaf.end());
    for (auto i:prev_leaf) {
      update(i);
    }
    int res = leaves - (int)prev_leaf.size() + sz;
    if (res & 1) {
      cout << -1 << '\n';
    } else {
      res = n - 1 + sz + get(1, n);
      cout << res << '\n';
    }
    
    for (auto i:prev_leaf) {
      update(i);
    }
    
    for (auto i:cur) {
      update(i);
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}
/*
7 3
1 2
1 3
3 4
2 5
5 6
2 7
1 1
3 1 2 2
3 6 1 2
*/

• 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