oj.uz

Submission #866381

# Submission time Handle Problem Language Result Execution time Memory
866381 2023-10-26T03:59:31 Z NeroZein Spring cleaning (CEOI20_cleaning) C++17
100 / 100
 133 ms 27416 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];
  //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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 30 ms 13148 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12636 KB Output is correct
2 Correct 12 ms 12380 KB Output is correct
3 Correct 32 ms 17628 KB Output is correct
4 Correct 39 ms 16840 KB Output is correct
5 Correct 43 ms 18388 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13112 KB Output is correct
2 Correct 13 ms 13472 KB Output is correct
3 Correct 48 ms 26144 KB Output is correct
4 Correct 63 ms 27416 KB Output is correct
5 Correct 36 ms 24840 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14172 KB Output is correct
2 Correct 17 ms 13636 KB Output is correct
3 Correct 8 ms 13404 KB Output is correct
4 Correct 9 ms 13764 KB Output is correct
5 Correct 10 ms 13912 KB Output is correct
6 Correct 24 ms 14428 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 15892 KB Output is correct
2 Correct 49 ms 15856 KB Output is correct
3 Correct 34 ms 14944 KB Output is correct
4 Correct 45 ms 17188 KB Output is correct
5 Correct 49 ms 17008 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 17736 KB Output is correct
2 Correct 93 ms 20536 KB Output is correct
3 Correct 110 ms 20564 KB Output is correct
4 Correct 77 ms 20048 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 30 ms 13148 KB Output is correct
3 Correct 14 ms 12636 KB Output is correct
4 Correct 12 ms 12380 KB Output is correct
5 Correct 32 ms 17628 KB Output is correct
6 Correct 39 ms 16840 KB Output is correct
7 Correct 43 ms 18388 KB Output is correct
8 Correct 13 ms 13112 KB Output is correct
9 Correct 13 ms 13472 KB Output is correct
10 Correct 48 ms 26144 KB Output is correct
11 Correct 63 ms 27416 KB Output is correct
12 Correct 36 ms 24840 KB Output is correct
13 Correct 26 ms 14172 KB Output is correct
14 Correct 17 ms 13636 KB Output is correct
15 Correct 8 ms 13404 KB Output is correct
16 Correct 9 ms 13764 KB Output is correct
17 Correct 10 ms 13912 KB Output is correct
18 Correct 24 ms 14428 KB Output is correct
19 Correct 40 ms 15892 KB Output is correct
20 Correct 49 ms 15856 KB Output is correct
21 Correct 34 ms 14944 KB Output is correct
22 Correct 45 ms 17188 KB Output is correct
23 Correct 49 ms 17008 KB Output is correct
24 Correct 72 ms 17736 KB Output is correct
25 Correct 93 ms 20536 KB Output is correct
26 Correct 110 ms 20564 KB Output is correct
27 Correct 77 ms 20048 KB Output is correct
28 Correct 47 ms 16728 KB Output is correct
29 Correct 69 ms 22876 KB Output is correct
30 Correct 45 ms 19412 KB Output is correct
31 Correct 62 ms 27320 KB Output is correct
32 Correct 46 ms 16988 KB Output is correct
33 Correct 79 ms 21332 KB Output is correct
34 Correct 133 ms 23148 KB Output is correct
35 Correct 114 ms 23196 KB Output is correct