Submission #391316

#	Time	Username	Problem	Language	Result	Execution time	Memory
391316		Hegdahl	Railway (BOI17_railway)	C++17	100 / 100	886 ms	30320 KiB

railway

#include <bits/stdc++.h>
#define ar array
 
using namespace std;
 
template<class S, class F>
struct SegTreeBase {
  
  vector<S> values;
  vector<F> queued;
  int lg2, offset;
 
  static constexpr int log2i(unsigned n) { return 32-__builtin_clz(--n); }
  SegTreeBase(const vector<S> &src)
    : lg2(log2i((int)src.size())), offset(1<<log2i((int)src.size())) {
    values.reserve(2*offset);
    values.resize(offset);
    values.insert(values.end(), src.begin(), src.end());
    values.resize(2*offset);
    queued.resize(offset);
    for (int i = offset-1; i > 0; --i) recalc(i);
  }
 
  void recalc(int I) {
    assert(I > 0 && I < offset);
    values[I] = values[2*I] * values[2*I+1];
  }
 
  void push(int I) {
    assert(I > 0 && I < offset);
    values[2*I] = queued[I] * values[2*I];
    values[2*I+1] = queued[I] * values[2*I+1];
    if (2*I < offset) {
      queued[2*I] = queued[I] * queued[2*I];
      queued[2*I+1] = queued[I] * queued[2*I+1];
    }
    queued[I] = F();
  }
 
  void push_col(int I) {
    assert(I >= offset && I < 2*offset);
    for (int lvl = lg2-1; lvl >= 0; --lvl)
      push((I>>lvl)/2);
  }
 
  void push_range(int I, int J) {
    assert(I+1 >= offset && I+1 < 2*offset);
    assert(J-1 >= offset && J-1 < 2*offset);
    assert(I+1 < J);
    for (int lvl = lg2-1; lvl >= 0; --lvl) {
      push(((I+1)>>lvl)/2);
      if (I+1 != J-1) push(((J-1)>>lvl)/2);
    }
  }
 
  void set(int i, S v) {
    assert(i >= 0 && i < offset);
    i += offset;
    push_col(i);
    values[i] = v;
    while (i /= 2) recalc(i);
  }
 
  void upd_node(int I, const F &f) {
    assert(I > 0 && I < 2*offset);
    values[I] = f * values[I];
    if (I < offset) queued[I] = f * queued[I];
  }
 
  void upd(int i, const F &f) {
    assert(i >= 0 && i < offset);
    i += offset;
    push_col(i);
    upd_node(i, f);
    while (i/=2) recalc(i);
  }
 
  void upd(int i, int j, const F &f) {
    assert(i >= 0 && i < offset);
    assert(j >= 0 && j < offset);
    assert(i <= j);
    i += offset-1;
    j += offset+1;
    int oi = i, oj = j;
    push_range(i, j);
    while (i+1 < j) {
      if ((i&1)==0) upd_node(i+1, f);
      if ((j&1)==1) upd_node(j-1, f);
      i >>= 1, j >>= 1;
    }
    i = oi+1, j = oj-1;
    for (int lvl = 1; lvl <= lg2; lvl++) {
      if (__builtin_ctz(i) < lvl) recalc(i >> lvl);
      if (__builtin_ctz(j+1) < lvl) recalc(j >> lvl);
    }
  }
 
  S qry(int i) {
    assert(i >= 0 && i < offset);
    i += offset;
    push_col(i);
    return values[i];
  }
 
  S qry(int i, int j) {
    assert(i >= 0 && i < offset);
    assert(j >= 0 && j < offset);
    assert(i <= j);
    i += offset-1;
    j += offset+1;
    push_range(i, j);
    S ls, rs;
    while (i+1 < j) {
      if ((i&1)==0) ls = ls * values[i+1];
      if ((j&1)==1) rs = values[j-1] * rs;
      i >>= 1, j >>= 1;
    }
    return ls * rs;
  }
 
  template<class Cmp>
  int upper_bound(S t, Cmp cmp) {
    if (cmp(values[1], t)) return offset;
    int lvl = lg2;
    int I = 1;
    S pre;
    while (lvl--) {
      I *= 2;
      push(I/2);
      if (cmp(pre*values[I], t)) {
        pre = pre*values[I];
        ++I;
      }
    }
    return I - offset;
  }
 
};
 
struct SumS {
  int w = 1;
  int s = 0;
  SumS operator*(const SumS &rhs) const {
    return {w+rhs.w, s+rhs.s};
  }
};
 
struct SumF {
  int sum = 0;
  SumF operator*(const SumF &rhs) const {
    return {rhs.sum+sum};
  }
  SumS operator*(const SumS &rhs) const {
    return {rhs.w, rhs.s + sum * rhs.w};
  }
};
 
struct TouchS {
  bool v = false;
  TouchS operator*(const TouchS &rhs) const {
    return {bool(v | rhs.v)};
  }
};
 
struct TouchF {
  bool s0 = false;
  bool s1 = false;
  TouchF operator*(const TouchF &rhs) const {
    if (s0) return {true, false};
    if (s1) return {false, true};
    return rhs;
  }
  TouchS operator*(const TouchS &rhs) const {
    if (s0) return {false};
    if (s1) return {true};
    return rhs;
  }
};
 
using SumST = SegTreeBase<SumS, SumF>;
using TouchST = SegTreeBase<TouchS, TouchF>;
 
const int mxN = 1e5;
 
vector<ar<int, 2>> g[mxN];
 
int sz[mxN];
int up_id[mxN];
int dof[mxN];
int up[20][mxN];
 
int dfs1(int cur, int prv, int d) {
  sz[cur] = 1;
  dof[cur] = d;
  for (auto [nxt, nn] : g[cur]) {
    if (nxt == prv) continue;
    sz[cur] += dfs1(nxt, cur, d+1);
    up_id[nxt] = nn;
    up[0][nxt] = cur;
  }
  return sz[cur];
}
 
int order[mxN];
int pof[mxN];
int chain_top[mxN];
 
void dfs2(int &I, int cur, int prv, int ct) {
  int heavy = -1;
  int heavy_sz = 0;
 
  order[I] = cur;
  pof[cur] = I++;
  chain_top[cur] = ct;
 
  for (auto [nxt, nn] : g[cur]) {
    if (nxt == prv) continue;
    if (sz[nxt] <= heavy_sz) continue;
    heavy = nxt;
    heavy_sz = sz[nxt];
  }
 
  if (heavy != -1) dfs2(I, heavy, cur, ct);
  for (auto [nxt, nn] : g[cur]) {
    if (nxt == prv) continue;
    if (nxt == heavy) continue;
    dfs2(I, nxt, cur, nxt);
  }
}
 
int lca(int i, int j) {
  if (dof[i] > dof[j]) swap(i, j);
 
  for (int lvl = 19; lvl >= 0; --lvl)
    if (dof[up[lvl][j]] >= dof[i])
      j = up[lvl][j];
 
  assert(dof[i] == dof[j]);
  if (i == j) return i;
 
 
  for (int lvl = 19; lvl >= 0; --lvl)
    if (up[lvl][i] != up[lvl][j])
      i = up[lvl][i], j = up[lvl][j];
  
  assert(i != j);
  i = up[0][i], j = up[0][j];
  assert(i == j);
 
  return i;
}
 
SumST *sum_st;
TouchST *touch_st;
 
int find_hi(int i, int j) {
  //cerr << "find_hi: " << i << ' ' << j << ' ';
  //assert(lca(i, j)==j);
 
  for (int lvl = 19; lvl >= 0; --lvl) {
    if (dof[up[lvl][i]] <= dof[j]) continue;
    if (touch_st->qry(pof[up[lvl][i]]).v) continue;
    i = up[lvl][i];
  }
 
  //cerr << i << '\n';
  return up[0][i];
}
 
void add(int i, int j) {
  //assert(lca(i, j)==j);
 
  //cerr << "add " << i << ' ' << j << '\n';
 
  while (chain_top[i] != chain_top[j]) {
    sum_st->upd(pof[chain_top[i]], pof[i], {1});
    i = up[0][chain_top[i]];
  }
 
  if (i != j)
    sum_st->upd(pof[j]+1, pof[i], {1});
}
 
void touch(int i, int j) {
  //assert(lca(i, j)==j);
 
  //cerr << "touch " << i << ' ' << j << '\n';
 
  while (chain_top[i] != chain_top[j]) {
    touch_st->upd(pof[chain_top[i]], pof[i], {false, true});
    i = up[0][chain_top[i]];
  }
 
  if (i != j)
    touch_st->upd(pof[j]+1, pof[i], {false, true});
}
 
void untouch(int i, int j) {
  //assert(lca(i, j)==j);
 
  //cerr << "untouch " << i << ' ' << j << '\n';
 
  while (chain_top[i] != chain_top[j]) {
    touch_st->upd(pof[chain_top[i]], pof[i], {true, false});
    i = up[0][chain_top[i]];
  }
 
  if (i != j)
    touch_st->upd(pof[j]+1, pof[i], {true, false});
}
 
int main() {
 
  int n, m, k; cin >> n >> m >> k;
 
  for (int nn = 1; nn < n; ++nn) {
    int i, j; cin >> i >> j; --i, --j;
    //cerr << "edge: " << i << ' ' << j << '\n';
 
    g[i].push_back({j, nn});
    g[j].push_back({i, nn});
  }
 
  dfs1(0, -1, 0);
 
  for (int lvl = 0; lvl < 19; ++lvl)
    for (int i = 0; i < n; ++i)
      up[lvl+1][i] = up[lvl][up[lvl][i]];
 
  {
    int I = 0;
    dfs2(I, 0, -1, 0);
    //assert(I==n);
  }       
 
  /*
  for (int i = 0; i < n; ++i)
    cerr << chain_top[i] << " \n"[i==n-1];
  for (int i = 0; i < n; ++i)
    cerr << order[i] << " \n"[i==n-1]; // */
 
  sum_st = new SumST(vector<SumS>(n, {1, 0}));
  touch_st = new TouchST(vector<TouchS>(n, {false}));
 
  int a[mxN];
  for (int mm = 0; mm < m; ++mm) {
    int s; cin >> s;
 
    //cerr << s << ": ";
    for (int ss = 0; ss < s; ++ss) {
      cin >> a[ss], --a[ss];
      //cerr << a[ss] << ' ';
    }
 
    int hi = a[0];
    for (int ss = 1; ss < s; ++ss)
      hi = lca(hi, a[ss]);
 
    //cerr << "- " << hi << '\n';
 
    for (int ss = 0; ss < s; ++ss) {
      if (a[ss] == hi) continue;
      add(a[ss], find_hi(a[ss], hi));
      touch(a[ss], hi);
 
      /*
      cerr << "touched: ";
      for (int i = 0; i < n; ++i)
        cerr << touch_st->qry(i).v << " \n"[i==n-1]; // */
 
      /*
      cerr << "sum: ";
      for (int i = 0; i < n; ++i)
        cerr << sum_st->qry(i).s << " \n"[i==n-1]; */
    }
 
    for (int ss = 0; ss < s; ++ss) {
      if (a[ss] == hi) continue;
      untouch(a[ss], hi);
 
      /*
      cerr << "touched: ";
      for (int i = 0; i < n; ++i)
        cerr << touch_st->qry(i).v << " \n"[i==n-1]; // */
    }
 
    //cerr << '\n';
  }
 
  vector<int> ans;
  for (int i = 0; i < n; ++i)
    if (sum_st->qry(i).s >= k)
      ans.push_back(up_id[order[i]]);
  sort(ans.begin(), ans.end());
 
  cout << ans.size() << '\n';
  for (int mm : ans)
    cout << mm << ' ';
  cout << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25