oj.uz

답안 #438624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
438624 2021-06-28T10:25:22 Z CyanForces 분수 공원 (IOI21_parks) C++17
5 / 100
 3500 ms 178460 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -