Submission #438655

#	Time	Username	Problem	Language	Result	Execution time	Memory
438655		CyanForces	Fountain Parks (IOI21_parks)	C++17	5 / 100	3590 ms	160900 KiB

parks

#include "parks.h"

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

#undef assert
#define assert(...) // ignore

const int inf = 1e9;

namespace LCT {

  /**
   * Description: Link-Cut Tree with possibility to augment.
   * \texttt{sz} is for path queries; 
   * \texttt{sub}, \texttt{vsub} are for subtree queries. \texttt{x->access()} 
   * brings \texttt{x} to the top of splay tree and propagates it (\textbf{call it!});
   * the left subtree will be
   * the path from \texttt{x} to the root and the right subtree will be empty. 
   * Then $\texttt{sub} = $ size of connected component
   * and $\texttt{vsub} = $ number of nodes below \texttt{x}.
   * \texttt{x->makeRoot()} ``rotates'' the tree so that \texttt{x} is root.
   * Use \texttt{x->makeRoot(), y->access(), y->sum} for path queries.
   * Time: O(\log N)
   * Usage: vector<sn> lct; rep(i,0,n) lct[i]=new snode(i); link(lct[0],lct[2],1); cut(lct[2],lct[0]);
   * Author: benq
   * Source: Dhruv Rohatgi, Eric Zhang, Benq
   * https://sites.google.com/site/kc97ble/container/splay-tree/splaytree-cpp-3
   * https://codeforces.com/blog/entry/67637
   * Status: tested on problems...
   */
  typedef struct snode* sn;
  struct snode { //////// VARIABLES
    sn p, c[2]; // parent, children
    bool flip = 0; // subtree flipped or not
    int val = -1;
    //int sz; // value in node, # nodes in current splay tree
    //int sub, vsub = 0; // vsub stores sum of virtual children
    int max_val = -1;
    snode(int _val) : val(_val) {
      p = c[0] = c[1] = NULL; calc(); }
    //friend int getSz(sn x) { return x?x->sz:0; }
    friend int get_max_val(sn x) { return x?x->max_val:-1; }
    //friend int getSub(sn x) { return x?x->sub:0; }

    void prop() { // lazy prop
      if (!flip) return;
      swap(c[0],c[1]); flip = 0;
      rep(i,0,2) if (c[i]) c[i]->flip ^= 1;
    }
    void calc() { // recalc vals
      rep(i,0,2) if (c[i]) c[i]->prop();
      //sz = 1+getSz(c[0])+getSz(c[1]);
      //sub = 1+getSub(c[0])+getSub(c[1])+vsub;
      max_val = max({val, get_max_val(c[0]), get_max_val(c[1])});
    }
    void set(int v) { access(); val = v; calc(); }
    // ============ SPLAY TREE OPERATIONS ==============
    int dir() {
      if (!p) return -2;
      rep(i,0,2) if (p->c[i] == this) return i;
      return -1; // p is path-parent pointer, not same splaytree
    }
    bool isRoot() { return dir() < 0; }  // of splaytree
    friend void setLink(sn x, sn y, int d) {
      if (y) y->p = x;
      if (d >= 0) x->c[d] = y; }
    void rot() { // assume p and p->p propagated
      assert(!isRoot()); int x = dir(); sn pa = p;
      setLink(pa->p, this, pa->dir());
      setLink(pa, c[x^1], x); setLink(this, pa, x^1);
      pa->calc();
    }
    void splay() {
      while (!isRoot() && !p->isRoot()) {
        p->p->prop(), p->prop(), prop();
        dir() == p->dir() ? p->rot() : rot();
        rot();
      }
      if (!isRoot()) p->prop(), prop(), rot();
      prop(); calc();
    }
    //sn fbo(int b) { // (optional) find by order
    //  prop(); int z = getSz(c[0]); // of splay tree
    //  if (b == z) { splay(); return this; }
    //  return b < z ? c[0]->fbo(b) : c[1] -> fbo(b-z-1);
    //}
    // ============ BASE OPERATIONS ==============
    void access() { // bring this to top of splaytree, propagate
      for (sn v = this, pre = NULL; v; v = v->p) {
        v->splay(); // now switch virtual children
        //if (pre) v->vsub -= pre->sub;
        //if (v->c[1]) v->vsub += v->c[1]->sub;
        v->c[1] = pre; v->calc(); pre = v;
      }
      splay(); assert(!c[1]); // right subtree is empty
    }
    void makeRoot() { // make root of real tree
      access(); flip ^= 1; access(); assert(!c[0] && !c[1]);
    }
    // ===================== QUERIES =====================
    friend bool connected(sn x, sn y) { return lca(x,y); } 
    friend sn lca(sn x, sn y) {
      if (x == y) return x;
      x->access(), y->access(); if (!x->p) return NULL;
      x->splay(); return x->p?:x;
    }
    //int distRoot() { access(); return getSz(c[0]); }
    //sn getRoot() { // get (real tree) root of component
    //  access(); sn a = this; 
    //  while (a->c[0]) a = a->c[0], a->prop();
    //  a->access(); return a;
    //}
    //sn getPar(int b) { // get b-th parent on path to root
    //  access(); b = getSz(c[0])-b; assert(b >= 0);
    //  return fbo(b); // can also get min, max on path to root...
    //}
    // ================= MODIFICATIONS =====================
    friend void link(sn x, sn y, bool force = 1) {
      assert(!connected(x,y)); // when force = 0,
      if (force) y->makeRoot(); // assumes y has no parent
      else { y->access(); assert(!y->c[0]); }
      x->access(); setLink(y,x,0); y->calc();
    }
    friend void cut(sn y) { // cut from parent
      y->access(); assert(y->c[0]);
      y->c[0]->p = NULL; y->c[0] = NULL; y->calc();
    }
    friend void cut(sn x, sn y) { // if x, y adj in tree
      x->makeRoot(); y->access(); 
      assert(y->c[0] == x && !x->c[0] && !x->c[1]); cut(y);
    }
  };

}


int n = 0; // number of ground elements

struct PartitionMatroid { // partition matroid
  vi cols;
  vector<vi> has_col;
  vi used_col;
  vi used;

  PartitionMatroid(vi c) : used(n) {
    cols = c;
    int mx = 0;
    for(int c : cols) mx = max(mx,c);
    has_col.resize(mx+1);
    used_col.resize(mx+1);
    rep(i,0,n) has_col[c[i]].emplace_back(i);
  }

  void add(int i) {
    //assert(!used[i]); assert(unused_cols.count(cols[i]));
    used_col[cols[i]] = 1;
    used[i] = 1;
  }

  void rem(int i) {
    //assert(used[i]); assert(!unused_cols.count(cols[i]));
    used_col[cols[i]] = 0;
    used[i] = 0;
  }

  int is_free(int b) { return !used_col[cols[b]]; }

  vi find_exchangeAB(int a) { // if we remove a, which b can we add?
    assert(used[a]);
    vi res;
    for(int b : has_col[cols[a]]) if(b != a) {
      assert(!used[b]);
      res.emplace_back(b);
    }
    return res;
  }
};

struct GraphicMatroid {
  vi u, v; // (u[i], v[i]) are the edges
  int m; // # graph nodes;
  vi bad, used;
  vector<LCT::sn> lct;
  vector<LCT::sn> lct_ed;
  vi activated;
  GraphicMatroid(vi a, vi b, int m) : u(a), v(b), m(m), bad(n), used(n) {
    lct.resize(m);
    lct_ed.resize(n);
    rep(i,0,m) lct[i] = new LCT::snode(-1);
    rep(i,0,n) lct_ed[i] = new LCT::snode(-1);
  }

  void add(int i) {
    assert(!used[i]);
    used[i] = 1;
    link(lct[u[i]], lct_ed[i]);
    link(lct[v[i]], lct_ed[i]);
  }

  void rem(int i) {
    assert(used[i]);
    used[i] = 0;
    cut(lct[u[i]], lct_ed[i]);
    cut(lct[v[i]], lct_ed[i]);
  }

  vi order, inv_order; // inv_order is priority
  void make_order(vi layers) {
    inv_order.assign(n,0);
    order.assign(n,0);
    iota(all(order),0);
    sort(all(order), [&](int i, int j){return layers[i] < layers[j];});
    rep(i,0,n) inv_order[order[i]] = i;
  }

  void clear_bad(vi layers) {
    make_order(layers);
    for(int i : activated) mark_bad(i);
    fill(all(bad),0);
    activated.clear();
    rep(i,0,n) if(used[i] && layers[i] != inf) {
      lct_ed[i]->set(inv_order[i]);
      activated.emplace_back(i);
    }
  }

  void mark_bad(int i) {
    if(bad[i]) return;
    bad[i] = 1;
    lct_ed[i]->set(-1);
  }

  bool is_free(int b) { // can we add b?
    assert(!used[b]);
    return !connected(lct[u[b]], lct[v[b]]);
  }

  int find_exchangeBA(int b) { // if we add b, which a should be removed?
    // just find a single out-edge!
    // We find it in maximum layer!
    assert(!used[b]);
    int x = u[b], y = v[b];
    assert(connected(lct[x], lct[y]));
    lct[x]->makeRoot();
    lct[y]->access();
    int res = lct[y]->max_val;
    if(res == -1) return -1;
    res = order[res];
    assert(!bad[res] && used[res]);
    return res;
  }

  ~GraphicMatroid(){
    rep(i,0,m) delete lct[i];
    rep(i,0,n) delete lct_ed[i];
  }
};

struct MatroidIsec {
  PartitionMatroid& m1;
  GraphicMatroid& m2;
  vi used;

  MatroidIsec(PartitionMatroid& m1, GraphicMatroid& m2) : m1(m1), m2(m2), used(n) {}


  vi layers;
  vi par;
  bool forward() {
    layers.assign(n, inf);
    par.assign(n, -1);

    m2.clear_bad(vi(n,0));

    queue<int> q;
    rep(b,0,n) if(m1.is_free(b)) {
      layers[b] = 0;
      par[b] = -2;
      q.push(b);
    }

    while(sz(q)) {
      int x = q.front();
      q.pop();

      if(used[x]) {
        int a = x;
        for(int b : m1.find_exchangeAB(a)) if(layers[b] == inf) {
          layers[b] = layers[a]+1;
          par[b] = a;
          q.push(b);
        }
      }
      else {
        int b = x, a;
        if(m2.is_free(b)) {
          debug(layers[b]);
          int x = b;
          rep(i,0,layers[b]+2) {
            debug(x);
            x = par[x];
          }
          return true; // found (s,t)-path!
        }

        while((a = m2.find_exchangeBA(b)) != -1) {
          assert(layers[a] == inf);
          m2.mark_bad(a);
          layers[a] = layers[b]+1;
          par[a] = b;
          q.push(a);
        }
      }
    }
    return false;
  }

  vi bad, aug;
  void push_flow() {
    bad.assign(n,0);
    m2.clear_bad(layers);
    vi todo;
    rep(i,0,n) if(layers[i] == 0) todo.emplace_back(i);

    bool found_one = false;

    for(int b : todo) {
      if(bad[b]) continue;
      if(!m1.is_free(b)) continue;
      aug.clear();
      if(dfs(b)) {
        //debug("AUG", aug);
        found_one = true;
        for(int i : aug) {
          bad[i] = true;
          m2.mark_bad(i);
        }
        for(int i : aug) if(used[i]) {
          m1.rem(i);
          m2.rem(i);
        }
        for(int i : aug) if(!used[i]) {
          m1.add(i);
          m2.add(i);
        }
        for(int i : aug) used[i] = !used[i];
        aug.clear();
      }
    }
    assert(found_one);
  }

  bool dfs(int x) {
    assert(!bad[x]);
    //bool DEB = (x == 310 || x == 308 || x == 322);
    //if(DEB) debug(x, layers[x]);

    if(used[x]) {
      int a = x;
      for(int b : m1.find_exchangeAB(a)) {
        //if(DEB) debug(a, b);
        if(layers[b] != layers[a]+1) continue;
        if(bad[b]) continue;
        if(dfs(b)) {
          aug.emplace_back(a);
          return true;
        }
      }
    }
    else {
      int b = x, a;
      //if(DEB) debug(b, m2.is_free(b));
      if(m2.is_free(b)) {
        aug.emplace_back(b);
        return true;
      }

      //if(DEB) debug(m2.activated, m2.activated.count(308));

      while((a = m2.find_exchangeBA(b)) != -1) {
        //if(a == 308) debug("HELLO");
        //if(DEB) debug(b, a);
        if(layers[a] != layers[b]+1) break;
        m2.mark_bad(a);
        if(dfs(a)) {
          aug.emplace_back(b);
          return true;
        }
      }
    }

    bad[x] = true;
    m2.mark_bad(x);
    return false;
  }

  void greedy() {
    rep(i,0,n) if(m1.is_free(i) && m2.is_free(i)) {
      used[i] = 1;
      m1.add(i);
      m2.add(i);
    }
  }

  void solve() {
    debug('%');
    debug("Greedy...");
    greedy();
    debug("done.", count(all(used),1));
    debug('%');
    debug("MI...");
    int cnt = 0;
    //debug(used);
    while(forward()) {
      debug("found path");
      push_flow();
      debug("phase", cnt++, count(all(used),1));
    }
    debug('%')
      debug("Done!")
  }

};

int construct_roads(std::vector<int> x, std::vector<int> y) {

  if(false) {
    x.clear();
    y.clear();
    rep(i,0,2000) rep(j,0,200) {
      if(rand()%2) {
        x.emplace_back(2*i);
        y.emplace_back(2*j);
      }
    }
    debug(sz(x));
  }

  map<pii,int> to_idx;
  rep(i,0,sz(x)) to_idx[pii(x[i],y[i])] = i;

  vi cols;
  vi u,v;
  auto add = [&](int x, int y, int c){
    ++n;
    u.emplace_back(x);
    v.emplace_back(y);
    cols.emplace_back(c);
  };


  int col = 0;
  map<pii,int> to_col;
  map<int,pii> from_col;
  auto which_col = [&](pii p) {
    if(!to_col.count(p)) {
      to_col[p] = col;
      from_col[col] = p;
      ++col;
    }
    return to_col[p];
  };

  rep(i,0,sz(x)) {
    if(to_idx.count(pii(x[i]+2,y[i]))) {
      int j = to_idx[pii(x[i]+2,y[i])];
      add(i,j,which_col(pii(x[i]+1, y[i]+1)));
      add(i,j,which_col(pii(x[i]+1, y[i]-1)));
    }
    if(to_idx.count(pii(x[i],y[i]+2))) {
      int j = to_idx[pii(x[i],y[i]+2)];
      add(i,j,which_col(pii(x[i]+1, y[i]+1)));
      add(i,j,which_col(pii(x[i]-1, y[i]+1)));
    }
  }

  //debug(cols); debug(u); debug(v);
  //
  debug(n);

  PartitionMatroid m1(cols);
  GraphicMatroid m2(u,v,sz(x));
  MatroidIsec mi(m1, m2);
  mi.solve();

  vi U, V, A, B;
  rep(i,0,n) if(mi.used[i]) {
    U.emplace_back(u[i]);
    V.emplace_back(v[i]);
    pii p = from_col[cols[i]];
    A.emplace_back(p.first);
    B.emplace_back(p.second);
  }
  assert(sz(U) < sz(x));
  if(sz(U) < sz(x)-1) return 0;

  build(U, V, A, B);
  return 1;
}

Compilation message (stderr)

parks.cpp: In member function 'void MatroidIsec::push_flow()':
parks.cpp:335:10: warning: variable 'found_one' set but not used [-Wunused-but-set-variable]
  335 |     bool found_one = false;
      |          ^~~~~~~~~
parks.cpp: In member function 'void MatroidIsec::solve()':
parks.cpp:422:9: warning: unused variable 'cnt' [-Wunused-variable]
  422 |     int cnt = 0;
      |         ^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30