Submission #1271592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271592		LucaLucaM	Spring cleaning (CEOI20_cleaning)	C++20	100 / 100	168 ms	18500 KiB

cleaning

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#pragma GCC optimize("O3")
// migrata de pe cses, sper ca intra si aici

using ll = long long;
#define debug(x) #x << " = " << x << '\n'
 
const int MAXN = 1e5;
 
std::vector<int> g[MAXN + 1];
 
void dfs0(int u, int p = -1) {
  if (p != -1) {
    g[u].erase(std::find(g[u].begin(), g[u].end(), p));
  }
  for (int v : g[u]) {
    dfs0(v, u);
  }
}
 
// ok acum s a redus la chestii de forma: lanturile astea le xorezi cu 1, spune suma
 
namespace AINT {
  struct Node {
    int cnt1, lazy;
    Node() : cnt1(0), lazy(0) {}
    Node operator + (const Node &other) const {
      Node ret;
      ret.cnt1 = cnt1 + other.cnt1;
      ret.lazy = 0;
      return ret;
    };
  };
  
  Node aint[4 * MAXN + 1];
  
  void push(int node, int tl, int tr) {
    if (aint[node].lazy) {
      if (tl != tr) {
        aint[2 * node].lazy ^= 1;
        aint[2 * node + 1].lazy ^= 1;
      }
      aint[node].cnt1 = tr - tl + 1 - aint[node].cnt1;
      aint[node].lazy = 0;
    }
  }
 
  void update(int node, int tl, int tr, int l, int r) {
    push(node, tl, tr);
    if (l <= tl && tr <= r) {
      aint[node].lazy ^= 1;
    } else {
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        update(2 * node, tl, mid, l, r);
      }
      if (mid < r) {
        update(2 * node + 1, mid + 1, tr, l, r);
      }
      push(2 * node, tl, mid);
      push(2 * node + 1, mid + 1, tr);
      aint[node] = aint[2 * node] + aint[2 * node + 1];
    }
  }
 
  int pointQuery(int node, int tl, int tr, int p) {
    push(node, tl, tr);
    if (tl == tr) {
      return aint[node].cnt1;
    } else {
      int mid = (tl + tr) / 2;
      if (p <= mid) {
        return pointQuery(2 * node, tl, mid, p);
      } else {
        return pointQuery(2 * node + 1, mid + 1, tr, p);
      }
    }
  }
  int query() {
    push(1, 1, MAXN);
    return aint[1].cnt1;
  }
};
 
namespace HLD {
  int tin[MAXN + 1];
  int head[MAXN + 1];
  int label[MAXN + 1];
  int sz[MAXN + 1];
  int heavySon[MAXN + 1];
  int parent[MAXN + 1];
 
  int timer = 0;
  int no_paths = 0;
 
  void dfs(int u) {
    sz[u] = 1;
    heavySon[u] = -1;
    for (int v : g[u]) {
      dfs(v);
      parent[v] = u;
      sz[u] += sz[v];
      if (heavySon[u] == -1 || sz[v] > sz[heavySon[u]]) {
        heavySon[u] = v;
      }
    }
  }
 
  void dfs2(int u) {
    tin[u] = ++timer;
    if (heavySon[u] != -1) {
      dfs2(heavySon[u]);
      label[u] = label[heavySon[u]];
    } else {
      label[u] = ++no_paths;
    }
    head[label[u]] = u;
 
    for (int v : g[u]) {
      if (v != heavySon[u]) {
        dfs2(v);
      }
    }
  }
 
  void init(int root) {
    dfs(root);
    dfs2(root);
  }
 
  void flipRange(int l, int r) {
    AINT::update(1, 1, MAXN, l, r);
  }
 
  void verticalUpdate(int u) {
    while (u) {
      flipRange(tin[head[label[u]]], tin[u]);
      u = parent[head[label[u]]];
    }
  }
 
  int pointQuery(int p) {
    return AINT::pointQuery(1, 1, MAXN, tin[p]);
  }
 
  int query() {
    return AINT::query();
  }
};
 
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
 
  int n, q;
  std::cin >> n >> q;
 
  for (int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
 
  int root = -1;
  for (int i = 1; i <= n; i++) {
    if ((int) g[i].size() >= 2) {
      root = i;
    }
  }
  assert(root != -1);
  
  dfs0(root);
  HLD::init(root);
 
  for (int i = 1; i <= n; i++) {
    if (g[i].empty()) {
      HLD::verticalUpdate(i);
    }
  }
 
  while (q--) {
    int k;
    std::cin >> k;
    std::vector<int> vert(k);
    int answer = 0;
    for (int &x : vert) {
      std::cin >> x;
      if (!g[x].empty()) {
        HLD::verticalUpdate(x);
      } 
      g[x].push_back(0);
      answer++;
    }
    
    int cnt1 = HLD::query();
    int cnt2 = n - cnt1;
    answer += cnt1;
    answer += 2 * cnt2;
    
    if (HLD::pointQuery(root)) {
      answer = -1;
    } else {
      answer -= 2;
    }
    // hbrnm ce se intampla in sursa asta, Doamne ajuta!!
     
    std::cout << answer << '\n';
    
    for (int x : vert) {
      g[x].pop_back();
      if (!g[x].empty()) {
        HLD::verticalUpdate(x);
      }
    }
 
  }
 
  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