Submission #788624

#	Time	Username	Problem	Language	Result	Execution time	Memory
788624		WLZ	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	146 ms	31220 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
 
int max_log, dfs_cnt = 0, e = 0;
vector< vector<int> > g, up, aux;
vector<int> dfs_in, dfs_out, d, s, leaves;
vector<bool> critical;

void dfs(int u, int p) {
  up[u][0] = p;
  dfs_in[u] = dfs_cnt++;
  for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (auto& v : g[u]) {
    if (v == p) continue;
    d[v] = d[u] + 1;
    dfs(v, u);
    leaves[u] += leaves[v];
  }
  dfs_out[u] = dfs_cnt;
  if ((int) g[u].size() == 1) leaves[u]++;  
}

void dfs2(int u, int p) {
  if (leaves[u] % 2 == 0) e++, s[u]++;
  for (auto& v : g[u]) {
    if (v != p) {
      s[v] += s[u];
      dfs2(v, u);
    }
  }
}

int dfs3(int u, int p, int &ans) {
  int cnt = 0;
  for (auto& v : aux[u]) {
    cnt += dfs3(v, u, ans);
  }
  if (critical[u]) cnt++;
  if (cnt % 2 == 1) {
    ans += d[u] - d[p] - 2 * (s[u] - s[p]);
  }
  return cnt;
}

bool is_anc(int u, int v) {
  return dfs_in[u] <= dfs_in[v] && dfs_out[u] >= dfs_out[v];
}

int lca(int u, int v) {
  if (is_anc(u, v)) return u;
  if (is_anc(v, u)) return v;
  for (int i = max_log; i >= 0; i--) {
    if (!is_anc(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  g.resize(n + 1);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int r = 1;
  while ((int) g[r].size() == 1) r++;
  max_log = ceil(log2(n));
  up.assign(n + 1, vector<int>(max_log + 1));
  dfs_in.resize(n + 1); dfs_out.resize(n + 1);
  d.assign(n + 1, 0);
  leaves.assign(n + 1, 0);
  d[r] = 1;
  dfs(r, r);
  s.assign(n + 1, 0);
  dfs2(r, -1);
  critical.assign(n + 1, false);
  aux.resize(n + 1);
  while (q--) {
    int d;
    cin >> d;
    map<int, int> mp;
    for (int i = 0; i < d; i++) {
      int x;
      cin >> x;
      mp[x]++;
    }
    vector<int> v;
    for (auto& p : mp) {
      if ((int) g[p.first].size() == 1 && p.second % 2 == 0) v.push_back(p.first);
      if ((int) g[p.first].size() > 1 && p.second % 2 == 1) v.push_back(p.first);
    }
    for (auto& x : v) critical[x] = true;
    sort(v.begin(), v.end(), [&](int a, int b) {
      return dfs_in[a] < dfs_in[b];
    });
    for (int i = 1, sz = (int) v.size(); i < sz; i++) {
      v.push_back(lca(v[i - 1], v[i]));
    }
    sort(v.begin(), v.end(), [&](int a, int b) {
      return dfs_in[a] < dfs_in[b];
    });
    v.erase(unique(v.begin(), v.end()), v.end());
    if (v.empty()) {
      if (leaves[r] % 2 == 0) cout << n + d + e - 2 << '\n';
      else cout << -1 << '\n';
      continue;
    }
    vector<int> st = {v[0]};
    for (int i = 1; i < (int) v.size(); i++) {
      while (!is_anc(st.back(), v[i])) st.pop_back();
      aux[st.back()].push_back(v[i]);
      st.push_back(v[i]);
    }
    int tmp = e;
    if ((leaves[r] + dfs3(st[0], 0, tmp)) % 2 == 0) {
      cout << n + d + tmp - 2 << '\n';
    } else {
      cout << -1 << '\n';
    }
    for (auto& x : v) {
      aux[x].clear();
      critical[x] = false;
    }
  }
  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