oj.uz

Submission #1087517

# Submission time Handle Problem Language Result Execution time Memory
1087517 2024-09-12T20:11:17 Z juicy Spring cleaning (CEOI20_cleaning) C++17
9 / 100
 166 ms 28752 KB 
#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;
      }
      add(u, i, u);
    }
    valid[i] = cnt % 2 == 0;
  }
  dfs(root, 0);
  for (auto [i, u] : st[root]) {
    upd(u, 0, i);
  }
  for (int i = 1; i <= q; ++i) {
    cout << (valid[i] ? ans + res[i] : -1) << "\n";
  }
  return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Incorrect 58 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9048 KB Output is correct
2 Correct 11 ms 9052 KB Output is correct
3 Correct 37 ms 28292 KB Output is correct
4 Correct 54 ms 28752 KB Output is correct
5 Correct 33 ms 26448 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Incorrect 58 ms 12892 KB Output isn't correct
3 Halted 0 ms 0 KB -