Submission #438624

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
438624	2021-06-28T10:25:22 Z	CyanForces	Fountain Parks (IOI21_parks)	C++17	5 / 100	3500 ms	178460 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;


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, 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;
  set<int> unused_cols;
  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);
    rep(i,0,n) has_col[c[i]].emplace_back(i);
    rep(i,0,sz(has_col)) unused_cols.emplace(i);
  }

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

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

  int is_free(int b) { return unused_cols.count(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;
  set<int> used_set;
  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;
    used_set.emplace(i);
    link(lct[u[i]], lct_ed[i]);
    link(lct[v[i]], lct_ed[i]);
  }

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

  void clear_bad() {
    fill(all(bad),0);
    for(int i : used_set) lct_ed[i]->set(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!
    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;
    assert(res == -1 || (!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) {}


  const int inf = 1e9;
  vi layers;
  bool forward() {
    layers.assign(n, inf);

    m2.clear_bad();

    queue<int> q;
    rep(b,0,n) if(m1.is_free(b)) {
      layers[b] = 0;
      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;
          q.push(b);
        }
      }
      else {
        int b = x, a;
        if(m2.is_free(b)) 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;
          q.push(a);
        }
      }
    }
    return false;
  }

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

    for(int b : todo) {
      if(bad[b]) continue;
      if(!m1.is_free(b)) continue;
      aug.clear();
      if(dfs(b)) {
        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();
      }
    }
  }

  bool dfs(int x) {
    assert(!bad[x]);

    if(used[x]) {
      int a = x;
      for(int b : m1.find_exchangeAB(a)) {
        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(m2.is_free(b)) {
        aug.emplace_back(b);
        return true;
      }

      while((a = m2.find_exchangeBA(b)) != -1) {
        m2.mark_bad(a);
        if(layers[a] != layers[b]+1) continue;
        if(dfs(a)) {
          aug.emplace_back(b);
          return true;
        }
      }
    }

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

  void solve() {
    debug(used);
    while(forward()) {
      push_flow();
      debug(used);
    }
  }

};

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

  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);

  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;
}

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	204 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	1560 ms	89500 KB	Output is correct
10	Correct	68 ms	9204 KB	Output is correct
11	Correct	401 ms	48500 KB	Output is correct
12	Correct	102 ms	13644 KB	Output is correct
13	Correct	321 ms	38520 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	14 ms	1996 KB	Output is correct
16	Correct	1639 ms	89428 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	204 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	1560 ms	89500 KB	Output is correct
10	Correct	68 ms	9204 KB	Output is correct
11	Correct	401 ms	48500 KB	Output is correct
12	Correct	102 ms	13644 KB	Output is correct
13	Correct	321 ms	38520 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	14 ms	1996 KB	Output is correct
16	Correct	1639 ms	89428 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	204 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	3597 ms	175116 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	204 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	1560 ms	89500 KB	Output is correct
10	Correct	68 ms	9204 KB	Output is correct
11	Correct	401 ms	48500 KB	Output is correct
12	Correct	102 ms	13644 KB	Output is correct
13	Correct	321 ms	38520 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	14 ms	1996 KB	Output is correct
16	Correct	1639 ms	89428 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	204 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	3597 ms	175116 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	204 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	1560 ms	89500 KB	Output is correct
10	Correct	68 ms	9204 KB	Output is correct
11	Correct	401 ms	48500 KB	Output is correct
12	Correct	102 ms	13644 KB	Output is correct
13	Correct	321 ms	38520 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	14 ms	1996 KB	Output is correct
16	Correct	1639 ms	89428 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	2583 ms	132808 KB	Output is correct
21	Correct	3144 ms	132568 KB	Output is correct
22	Correct	2842 ms	132492 KB	Output is correct
23	Correct	3125 ms	152084 KB	Output is correct
24	Correct	397 ms	30020 KB	Output is correct
25	Correct	3258 ms	172772 KB	Output is correct
26	Correct	3385 ms	172784 KB	Output is correct
27	Execution timed out	3607 ms	171264 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	204 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	1560 ms	89500 KB	Output is correct
10	Correct	68 ms	9204 KB	Output is correct
11	Correct	401 ms	48500 KB	Output is correct
12	Correct	102 ms	13644 KB	Output is correct
13	Correct	321 ms	38520 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	14 ms	1996 KB	Output is correct
16	Correct	1639 ms	89428 KB	Output is correct
17	Correct	3481 ms	178456 KB	Output is correct
18	Correct	3292 ms	178460 KB	Output is correct
19	Correct	2757 ms	132544 KB	Output is correct
20	Execution timed out	3609 ms	154396 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	204 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	1560 ms	89500 KB	Output is correct
10	Correct	68 ms	9204 KB	Output is correct
11	Correct	401 ms	48500 KB	Output is correct
12	Correct	102 ms	13644 KB	Output is correct
13	Correct	321 ms	38520 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	14 ms	1996 KB	Output is correct
16	Correct	1639 ms	89428 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	204 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	3597 ms	175116 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Submission #438624

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