Submission #1146301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146301		ind1v	Spring cleaning (CEOI20_cleaning)	C++17	100 / 100	263 ms	19696 KiB

cleaning

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct segment_tree {
  struct node {
    int cnt[2];
    
    node() {
      memset(cnt, 0, sizeof(cnt));
    }
    
    node operator + (const node &o) {
      node res;
      res.cnt[0] = this->cnt[0] + o.cnt[0];
      res.cnt[1] = this->cnt[1] + o.cnt[1];
      return res;
    }
  } t[4 * N];
  
  bool lz[4 * N];
  
  segment_tree() {
    memset(lz, false, sizeof(lz));
  }
  
  void push(int id) {
    swap(t[id << 1].cnt[0], t[id << 1].cnt[1]);
    lz[id << 1] ^= lz[id];
    swap(t[id << 1 | 1].cnt[0], t[id << 1 | 1].cnt[1]);
    lz[id << 1 | 1] ^= lz[id];
    lz[id] = false;
  }
  
  void build(int id, int tl, int tr) {
    if (tl == tr) {
      t[id].cnt[0] = 1;
      return;
    }
    int tm = (tl + tr) >> 1;
    build(id << 1, tl, tm);
    build(id << 1 | 1, tm + 1, tr);
    t[id] = t[id << 1] + t[id << 1 | 1];
  }
  
  void flip(int id, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      swap(t[id].cnt[0], t[id].cnt[1]);
      lz[id] ^= 1;
      return;
    }
    if (lz[id]) {
      push(id);
    }
    int tm = (tl + tr) >> 1;
    if (r <= tm) {
      flip(id << 1, tl, tm, l, r);
    } else if (tm + 1 <= l) {
      flip(id << 1 | 1, tm + 1, tr, l, r);
    } else {
      flip(id << 1, tl, tm, l, r);
      flip(id << 1 | 1, tm + 1, tr, l, r);
    }
    t[id] = t[id << 1] + t[id << 1 | 1];
  }
};

int n, q;
vector<int> g[N];
int sz[N], son[N], h[N], pos[N], lv[N], fa[N], deg[N];
int time_hld = 0, leaf_cnt = 0;
segment_tree st;

void pre_dfs(int u, int p) {
  sz[u] = 1;
  int mx = -1;
  leaf_cnt += (deg[u] == 1);
  for (int v : g[u]) {
    if (v != p) {
      fa[v] = u;
      lv[v] = lv[u] + 1;
      pre_dfs(v, u);
      sz[u] += sz[v];
      if (sz[v] > mx) {
        mx = sz[v];
        son[u] = v;
      }
    }
  }
}

void decompose(int u, int p, int f) {
  pos[u] = ++time_hld;
  h[u] = f;
  if (son[u] != 0) {
    decompose(son[u], u, f);
  }
  for (int v : g[u]) {
    if (v != p && v != son[u]) {
      decompose(v, u, v);
    }
  }
}

void upd(int u) {
  while (h[u] != 1) {
    st.flip(1, 1, n, pos[h[u]], pos[u]);
    u = fa[h[u]];
  }
  if (pos[1] < pos[u]) {
    st.flip(1, 1, n, pos[1] + 1, pos[u]);
  }
}

void dfs(int u, int p) {
  if (deg[u] == 1) {
    upd(u);
  }
  for (int v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
    deg[u]++;
    deg[v]++;
  }
  pre_dfs(1, 1);
  decompose(1, 1, 1);
  st.build(1, 1, n);
  dfs(1, 1);
  while (q--) {
    int l = leaf_cnt;
    int d;
    cin >> d;
    vector<int> a(d);
    for (int &x : a) {
      cin >> x;
    }
    vector<int> redo;
    for (int x : a) {
      l -= (deg[x] == 1);
      l++;
      if (deg[x] == 1) {
        upd(x);
        redo.emplace_back(x);
      }
      deg[x]++;
      upd(x);
    }
    for (int x : a) {
      deg[x]--;
    }
    if (l & 1) {
      cout << -1 << '\n';
    } else {
      cout << st.t[1].cnt[0] * 2 + st.t[1].cnt[1] + d - 2 << '\n';
    }
    for (int x : a) {
      upd(x);
    }
    for (int x : redo) {
      upd(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