Submission #148147

#	Time	Username	Problem	Language	Result	Execution time	Memory
148147		Xylofo	Split the Attractions (IOI19_split)	C++14	100 / 100	501 ms	56868 KiB

split

#include "split.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


#ifdef LOCAL
#include "../../../../MixedFunc/pretty_debug.h"
#else
#define debug(...) //ignore
#endif

struct stOrder {
  vector<vi> g;
  vi pre, low, P;
  int Time;
  vi preO;
  stOrder(vector<vi> &g) : g(g), pre(sz(g),0), low(sz(g),0), P(sz(g),0) {}

  int dfs(int at, int par) {
    preO.eb(at);
    P[at] = par;
    pre[at] = ++Time;
    low[at] = at;
    trav(y, g[at]) if (y != par) {
      int up = pre[y] ? y : dfs(y,at);
      if(pre[up] < pre[low[at]]) low[at] = up;
    }
    return low[at];
  }

  vi order(int s){
    dfs(s,-1);
    int t = preO[1];
    vector<list<int>::iterator> pos(sz(g));
    list<int> L;
    pos[s] = L.insert(L.end(), s);
    pos[t] = L.insert(L.end(), t);
    vi sign(sz(g));
    sign[s] = -1;
    rep(i,2,sz(g)) {
      int x = preO[i];
      auto it = pos[P[x]];
      assert(sign[low[x]] != 0);
      if(sign[low[x]] == 1) it++;
      pos[x] = L.insert(it, x);
      sign[P[x]] = -sign[low[x]];
    }
    rep(i,0,sz(g)) assert(*pos[i] == i);
    return vi(all(L));
  }
};

vi num, st, top;
vector<vector<pii>> ed;
int Time;
template<class F>
int dfs(int at, int par, F& f) {
  int me = num[at] = ++Time, e, y, top = me;
  trav(pa, ed[at]) if (pa.second != par) {
    tie(y, e) = pa;
    if (num[y]) {
      top = min(top, num[y]);
      if (num[y] < me) st.push_back(e);
    } else {
      int si = sz(st);
      int up = dfs(y, e, f);
      top = min(top, up);
      if (up == me) {
        st.push_back(e);
        f(vi(st.begin() + si, st.end()));
        st.resize(si);
      }
      else if (up < me) st.push_back(e);
      else f({e}); // e is a bridge
    }
  }
  return top;
}

template<class F>
void bicomps(F f) {
  num.assign(sz(ed), 0);
  rep(i,0,sz(ed)) if (!num[i]) dfs(i, -1, f);
}

const vi BAD{};

vector<int> find_split(int n, int a, int b, int c, vi p, vi q) {

  debug(n,a,b,c);
  debug(p);
  debug(q);

  // tries to find a split into 2 connected comps.
  auto split = [&](){

    // find split with side in [L,R] works.
    int k = min({a,b,c}); 
    int L = k, R = n-k;
    debug(L,R);

    ed.resize(n);
    rep(i,0,sz(p)) {
      ed[p[i]].emplace_back(q[i], i);
      ed[q[i]].emplace_back(p[i], i);
    }

    vector<vi> cmpEd(n); // e-ids in component
    vector<vi> bt(n); // block-tree(?): tree of verts and bcc, with edges between them.

    bicomps([&](const vi& edg){
        int C = sz(bt);
        bt.eb();
        cmpEd.eb(edg);
        trav(i,edg) bt[C].eb(p[i]), bt[C].eb(q[i]);
        sort(all(bt[C]));
        bt[C].resize(unique(all(bt[C])) - bt[C].begin());
        trav(i,bt[C]) bt[i].eb(C);
    });

    // precal subtree sizes
    vi siz(sz(bt)), par(sz(bt));
    function<int(int,int)> dfs = [&](int x, int p) {
      par[x] = p;
      if(x < n) ++siz[x];
      trav(y, bt[x]) if(y != p) siz[x] += dfs(y, x);
      return siz[x];
    };
    dfs(0,-1);
    debug(siz);

    auto comp = [&](int C) {
      auto &cmp = bt[C];
      int nc = sz(cmp);
      debug(nc, cmp);

      // build graph for bcc
      unordered_map<int,int> toCmpId;
      rep(i,0,nc) toCmpId[cmp[i]] = i;
      vector<vi> G(nc);
      trav(e, cmpEd[C]) {
        int a = toCmpId[p[e]], b = toCmpId[q[e]];
        G[a].eb(b);
        G[b].eb(a);
      }

      // calculated sizes of subtrees routed at each node
      vi ssz(nc,0);
      int rt = -1;
      rep(i,0,nc) {
        int x = cmp[i];
        if(par[x] == C) ssz[i] = siz[x];
        else rt = i;
      }
      assert(rt != -1);
      ssz[rt] = n - accumulate(all(ssz),0);

      debug(ssz);

      int mx = max_element(all(ssz)) - ssz.begin();
      //int mn = (mx ? 0 : 1); // mn != mx.

      if(ssz[mx] > R) return BAD; 

      // start building split
      int S = 0, cnt = 0;

      stOrder st(G);
      vi sp = st.order(mx);

      // now we extend S until S is in [L,R]
      // Note: not sure bfs actually works for this?
      while(S < L) S += ssz[sp[cnt++]];
      assert(L <= S && S <= R);
      sp.resize(cnt);

      // construct answer
      vi ans;
      function<void(int,int)> dfs2 = [&](int x, int p) {
        if(x < n) ans.eb(x);
        trav(y, bt[x]) if(y != p) dfs2(y, x);
      };
      trav(i,sp) dfs2(cmp[i], C);
      assert(sz(ans) == S);
      return ans;
    };

    rep(C,n,sz(bt)) {
      auto sp = comp(C);
      if(sp != BAD) return sp;
    }
    return BAD;
  };

  vi sp = split();
  if(sp == BAD) return vi(n,0);
  debug(sp);

  // find other side of split
  sort(all(sp));
  vi spC;
  for(int i = 0, j = 0; i < n; ++i) {
    if(j < sz(sp) && sp[j] == i) ++j;
    else spC.eb(i);
  }
  if(sz(sp) > sz(spC)) swap(sp, spC);

  // color vertices
  vector<pii> Q = {{a,1}, {b,2}, {c,3}};
  sort(all(Q));
  vi res(n, Q[2].second);

  auto color = [&](vi &vert, int sz, int col) {
    assert(!vert.empty());
    assert(sz <= sz(vert));
    function<void(int)> f = [&](int x) {
      if(!binary_search(all(vert), x)) return;
      if(res[x] == col) return;
      if(sz == 0) return;
      res[x] = col; --sz;
      trav(y, ed[x]) f(y.first);
    };
    f(vert[0]);
    assert(sz == 0);
  };
  color(sp,  Q[0].first, Q[0].second);
  color(spC, Q[1].first, Q[1].second);

  return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36