oj.uz

Submission #866380

# Submission time Handle Problem Language Result Execution time Memory
866380 2023-10-26T03:52:54 Z NeroZein Spring cleaning (CEOI20_cleaning) C++17
26 / 100
 90 ms 22608 KB 
#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];
  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); 
    }
    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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Incorrect 28 ms 13296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12380 KB Output is correct
2 Correct 11 ms 12804 KB Output is correct
3 Correct 34 ms 18444 KB Output is correct
4 Correct 37 ms 17868 KB Output is correct
5 Correct 54 ms 19656 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 13912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15932 KB Output is correct
2 Incorrect 56 ms 15644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 17884 KB Output is correct
2 Correct 71 ms 22352 KB Output is correct
3 Correct 90 ms 22608 KB Output is correct
4 Correct 69 ms 21844 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Incorrect 28 ms 13296 KB Output isn't correct
3 Halted 0 ms 0 KB -