Submission #438655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438655	2021-06-28T11:28:08 Z	CyanForces	Fountain Parks (IOI21_parks)	C++17	5 / 100	3500 ms	160900 KB

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

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	280 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1313 ms	78096 KB	Output is correct
10	Correct	51 ms	8132 KB	Output is correct
11	Correct	286 ms	42228 KB	Output is correct
12	Correct	74 ms	12020 KB	Output is correct
13	Correct	252 ms	33536 KB	Output is correct
14	Correct	6 ms	972 KB	Output is correct
15	Correct	11 ms	1740 KB	Output is correct
16	Correct	1353 ms	78124 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	280 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1313 ms	78096 KB	Output is correct
10	Correct	51 ms	8132 KB	Output is correct
11	Correct	286 ms	42228 KB	Output is correct
12	Correct	74 ms	12020 KB	Output is correct
13	Correct	252 ms	33536 KB	Output is correct
14	Correct	6 ms	972 KB	Output is correct
15	Correct	11 ms	1740 KB	Output is correct
16	Correct	1353 ms	78124 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	224 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Execution timed out	3584 ms	160900 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	280 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1313 ms	78096 KB	Output is correct
10	Correct	51 ms	8132 KB	Output is correct
11	Correct	286 ms	42228 KB	Output is correct
12	Correct	74 ms	12020 KB	Output is correct
13	Correct	252 ms	33536 KB	Output is correct
14	Correct	6 ms	972 KB	Output is correct
15	Correct	11 ms	1740 KB	Output is correct
16	Correct	1353 ms	78124 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	224 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Execution timed out	3584 ms	160900 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	280 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1313 ms	78096 KB	Output is correct
10	Correct	51 ms	8132 KB	Output is correct
11	Correct	286 ms	42228 KB	Output is correct
12	Correct	74 ms	12020 KB	Output is correct
13	Correct	252 ms	33536 KB	Output is correct
14	Correct	6 ms	972 KB	Output is correct
15	Correct	11 ms	1740 KB	Output is correct
16	Correct	1353 ms	78124 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	2051 ms	119284 KB	Output is correct
21	Correct	2577 ms	119284 KB	Output is correct
22	Correct	2242 ms	119268 KB	Output is correct
23	Correct	2558 ms	133372 KB	Output is correct
24	Correct	440 ms	26864 KB	Output is correct
25	Correct	2785 ms	150408 KB	Output is correct
26	Correct	2843 ms	150424 KB	Output is correct
27	Execution timed out	3590 ms	151292 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	280 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1313 ms	78096 KB	Output is correct
10	Correct	51 ms	8132 KB	Output is correct
11	Correct	286 ms	42228 KB	Output is correct
12	Correct	74 ms	12020 KB	Output is correct
13	Correct	252 ms	33536 KB	Output is correct
14	Correct	6 ms	972 KB	Output is correct
15	Correct	11 ms	1740 KB	Output is correct
16	Correct	1353 ms	78124 KB	Output is correct
17	Correct	3138 ms	156072 KB	Output is correct
18	Correct	3030 ms	156028 KB	Output is correct
19	Correct	2361 ms	119280 KB	Output is correct
20	Execution timed out	3582 ms	143688 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	280 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1313 ms	78096 KB	Output is correct
10	Correct	51 ms	8132 KB	Output is correct
11	Correct	286 ms	42228 KB	Output is correct
12	Correct	74 ms	12020 KB	Output is correct
13	Correct	252 ms	33536 KB	Output is correct
14	Correct	6 ms	972 KB	Output is correct
15	Correct	11 ms	1740 KB	Output is correct
16	Correct	1353 ms	78124 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	224 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Execution timed out	3584 ms	160900 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Submission #438655

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0