Submission #1087526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087526		juicy	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	98 ms	28756 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 5;

int n, q;
int dep[N], cnt[N], res[N], sz[N], vis[N];
bool valid[N];
vector<int> g[N];
set<array<int, 2>> st[N];

void upd(int u, int p, int i) {
  int h = dep[u] - dep[p], c = cnt[u] - cnt[p];
  res[i] += 2 * c - h;
}

void add(int u, int i, int x) {
  auto it = st[u].lower_bound({i, 0});
  if (it != st[u].end() && (*it)[0] == i) {
    upd((*it)[1], u, i);
    upd(x, u, i);
    st[u].erase(it);
  } else {
    st[u].insert({i, x});
  }
}

int calc(int u, int p) {
  sz[u] = g[u].size() == 1;
  int res = 0;
  for (int v : g[u]) {
    if (v ^ p) {
      res += calc(v, u) + (sz[v] & 1 ? 1 : 2);
      sz[u] += sz[v];
    }
  }
  return res;
}

void dfs(int u, int p) {
  dep[u] = dep[p] + 1;
  cnt[u] = cnt[p] + (sz[u] & 1);
  for (int v : g[u]) {
    if (v ^ p) {
      dfs(v, u);
      if (st[u].size() < st[v].size()) {
        st[u].swap(st[v]);
      }
      for (auto [x, y] : st[v]) {
        add(u, x, y);
      }
      set<array<int, 2>>().swap(st[v]);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int root = -1;
  for (int i = 1; i <= n; ++i) {
    if (g[i].size() > 1) {
      root = i;
    }
  }
  int ans = calc(root, root);
  for (int i = 1; i <= q; ++i) {
    int d; cin >> d;
    res[i] = d;
    int cnt = sz[root] + d;
    while (d--) {
      int u; cin >> u;
      if (vis[u] != i && g[u].size() == 1) {
        vis[u] = i;
        --cnt;
        continue;
      }
      add(u, i, u);
    }
    valid[i] = cnt % 2 == 0;
  }
  dfs(root, 0);
  for (auto [i, u] : st[root]) {
    upd(u, root, i);
  }
  for (int i = 1; i <= q; ++i) {
    cout << (valid[i] ? ans + res[i] : -1) << "\n";
  }
  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