Submission #866381

#	Time	Username	Problem	Language	Result	Execution time	Memory
866381		NeroZein	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	133 ms	27416 KiB

cleaning

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 1e5 + 5;
const int LOG = 18; 

vector<int> g[N]; 
vector<int> vg[N]; 

int ans; 
bool isCrit[N]; 
int leaves[N], ev[N]; 
int cnt, in[N], out[N];  
int pr[LOG][N], dep[N]; 

void dfs(int v, int p) {
  if (g[v].size() == 1) {
    leaves[v] = 1; 
  }
  in[v] = cnt++; 
  for (int u : g[v]) {
    if (u == p) {
      continue;
    }
    pr[0][u] = v;
    for (int j = 1; j < LOG; ++j) {
      pr[j][u] = pr[j - 1][pr[j - 1][u]]; 
    }
    dep[u] = dep[v] + 1; 
    dfs(u, v); 
    leaves[v] += leaves[u]; 
  }
  out[v] = cnt - 1;
}

void dfs2(int v, int p) {
  int t = leaves[v] % 2 == 0; 
  ans += t; 
  ev[v] += t; 
  for (int u : g[v]) {
    if (u == p) {
      continue;
    }
    ev[u] += ev[v];
    dfs2(u, v); 
  }
}

int isParent(int u, int v) {
  return in[v] <= in[u] && out[v] >= out[u]; 
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = pr[j][u]; 
    }
  }
  if (u == v) {
    return u; 
  }
  for (int j = LOG - 1; j >= 0; --j) {
    if (pr[j][u] != pr[j][v]) {
      u = pr[j][u], v = pr[j][v]; 
    }
  }
  return pr[0][u];
}

bool dfs3(int v, int p, int& add) {
  bool crit = isCrit[v];
  //deb(v) cout << '\n';
  for (int u : vg[v]) {
    if (u == p) {
      continue; 
    }
    crit ^= dfs3(u, v, add); 
  }
  if (crit) {
    add += dep[v] - dep[p] - 2 * (ev[v] - ev[p]); 
  }
  return crit; 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  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; 
  for (int i = 1; i <= n; ++i) {
    if (g[i].size() > 1) {
      r = i;
      break; 
    }
  }
  dfs(r, r); 
  dfs2(r, r); 
  ans += n - 1 - (ev[r]); 
  while (q--) {
    bool odd = leaves[r] % 2; 
    int d;
    cin >> d;
    vector<int> a(d);
    for (int i = 0; i < d; ++i) {
      cin >> a[i];
    }
    sort(a.begin(), a.end()); 
    vector<int> critical; 
    for (int i = 0; i < d; ++i) {
      bool od = true; 
      int j = i;
      while (j + 1 < d && a[j + 1] == a[j]) {
        j++;
        od ^= 1; 
      }
      od ^= (g[a[i]].size() == 1); 
      if (od) {
        odd ^= 1; 
        critical.push_back(a[i]); 
      }
      i = j; 
    }
    if (odd) {
      cout << -1 << '\n';
      continue;
    }
    critical.push_back(r); 
    sort(critical.begin(), critical.end(), [&](int i, int j) {
      return in[i] < in[j]; 
    });
    isCrit[critical.back()] = true; 
    for (int i = critical.size() - 1; i > 0; --i) {
      isCrit[critical[i - 1]] = true; 
      critical.push_back(lca(critical[i], critical[i - 1])); 
    }
    sort(critical.begin(), critical.end(), [&](int i, int j) {
      return in[i] < in[j]; 
    });
    critical.resize(unique(critical.begin(), critical.end()) - critical.begin());
    stack<int> stk; 
    stk.push(r);
    for (int i = 1; i < (int) critical.size(); ++i) {
      int v = critical[i]; 
      while (true) {
        assert(!stk.empty()); 
        int top = stk.top();
        if (!isParent(v, top)) {
          stk.pop();
        } else {
          break; 
        }
      }
      vg[stk.top()].push_back(v); 
      stk.push(v);
    }
    int add = d;
    dfs3(r, r, add); 
    cout << ans + add << '\n'; 
    for (int v : critical) {
      isCrit[v] = false; 
      vg[v].clear(); 
    }
  }
  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