oj.uz

답안 #148051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148051 2019-08-31T12:23:57 Z Xylofo Split the Attractions (IOI19_split) C++14
40 / 100
 325 ms 47968 KB 
#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

vi num, st;
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
      vi sp = {mx};
      vi added(nc);
      added[mx] = 1;
      int S = 0, bfs = 0;

      // now we extend S until S is in [L,R]
      // Note: not sure bfs actually works for this?
      while(S < L) {
        assert(bfs < sz(sp));
        int x = sp[bfs++];
        S += ssz[x];
        trav(y, G[x]) if(!added[y]) {
          sp.eb(y);
          added[y] = 1;
        }
      }
      assert(L <= S && S <= R);
      sp.resize(bfs);

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 508 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 301 ms 47968 KB ok, correct split
8 Correct 259 ms 45856 KB ok, correct split
9 Correct 289 ms 45976 KB ok, correct split
10 Correct 238 ms 45016 KB ok, correct split
11 Correct 256 ms 45532 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 239 ms 32992 KB ok, correct split
5 Correct 296 ms 30944 KB ok, correct split
6 Correct 209 ms 45228 KB ok, correct split
7 Correct 275 ms 45988 KB ok, correct split
8 Correct 278 ms 27136 KB ok, correct split
9 Correct 179 ms 20004 KB ok, correct split
10 Correct 201 ms 30968 KB ok, correct split
11 Correct 208 ms 31100 KB ok, correct split
12 Correct 210 ms 31384 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 323 ms 30840 KB ok, correct split
3 Correct 86 ms 12704 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 286 ms 36356 KB ok, correct split
6 Correct 285 ms 35780 KB ok, correct split
7 Correct 300 ms 35464 KB ok, correct split
8 Correct 325 ms 38632 KB ok, correct split
9 Correct 309 ms 35004 KB ok, correct split
10 Correct 81 ms 10328 KB ok, no valid answer
11 Correct 125 ms 15204 KB ok, no valid answer
12 Correct 241 ms 30236 KB ok, no valid answer
13 Correct 273 ms 30112 KB ok, no valid answer
14 Correct 224 ms 30508 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB ok, correct split
2 Correct 2 ms 376 KB ok, no valid answer
3 Correct 2 ms 256 KB ok, correct split
4 Correct 3 ms 256 KB ok, correct split
5 Correct 6 ms 376 KB ok, correct split
6 Correct 2 ms 396 KB ok, correct split
7 Correct 2 ms 376 KB ok, correct split
8 Correct 2 ms 256 KB ok, correct split
9 Correct 7 ms 1144 KB ok, correct split
10 Correct 6 ms 1016 KB ok, correct split
11 Correct 2 ms 376 KB ok, correct split
12 Correct 8 ms 1144 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 256 KB ok, correct split
15 Correct 2 ms 376 KB ok, correct split
16 Correct 2 ms 376 KB ok, correct split
17 Correct 2 ms 376 KB ok, correct split
18 Correct 2 ms 256 KB ok, correct split
19 Correct 3 ms 504 KB ok, correct split
20 Correct 4 ms 760 KB ok, correct split
21 Correct 7 ms 1272 KB ok, correct split
22 Correct 7 ms 1144 KB ok, correct split
23 Correct 7 ms 1272 KB ok, correct split
24 Correct 8 ms 1144 KB ok, correct split
25 Correct 7 ms 1192 KB ok, correct split
26 Runtime error 9 ms 2292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 508 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 301 ms 47968 KB ok, correct split
8 Correct 259 ms 45856 KB ok, correct split
9 Correct 289 ms 45976 KB ok, correct split
10 Correct 238 ms 45016 KB ok, correct split
11 Correct 256 ms 45532 KB ok, correct split
12 Correct 2 ms 256 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 239 ms 32992 KB ok, correct split
16 Correct 296 ms 30944 KB ok, correct split
17 Correct 209 ms 45228 KB ok, correct split
18 Correct 275 ms 45988 KB ok, correct split
19 Correct 278 ms 27136 KB ok, correct split
20 Correct 179 ms 20004 KB ok, correct split
21 Correct 201 ms 30968 KB ok, correct split
22 Correct 208 ms 31100 KB ok, correct split
23 Correct 210 ms 31384 KB ok, correct split
24 Correct 2 ms 256 KB ok, correct split
25 Correct 323 ms 30840 KB ok, correct split
26 Correct 86 ms 12704 KB ok, correct split
27 Correct 2 ms 376 KB ok, correct split
28 Correct 286 ms 36356 KB ok, correct split
29 Correct 285 ms 35780 KB ok, correct split
30 Correct 300 ms 35464 KB ok, correct split
31 Correct 325 ms 38632 KB ok, correct split
32 Correct 309 ms 35004 KB ok, correct split
33 Correct 81 ms 10328 KB ok, no valid answer
34 Correct 125 ms 15204 KB ok, no valid answer
35 Correct 241 ms 30236 KB ok, no valid answer
36 Correct 273 ms 30112 KB ok, no valid answer
37 Correct 224 ms 30508 KB ok, no valid answer
38 Correct 2 ms 380 KB ok, correct split
39 Correct 2 ms 376 KB ok, no valid answer
40 Correct 2 ms 256 KB ok, correct split
41 Correct 3 ms 256 KB ok, correct split
42 Correct 6 ms 376 KB ok, correct split
43 Correct 2 ms 396 KB ok, correct split
44 Correct 2 ms 376 KB ok, correct split
45 Correct 2 ms 256 KB ok, correct split
46 Correct 7 ms 1144 KB ok, correct split
47 Correct 6 ms 1016 KB ok, correct split
48 Correct 2 ms 376 KB ok, correct split
49 Correct 8 ms 1144 KB ok, correct split
50 Correct 2 ms 376 KB ok, correct split
51 Correct 2 ms 256 KB ok, correct split
52 Correct 2 ms 376 KB ok, correct split
53 Correct 2 ms 376 KB ok, correct split
54 Correct 2 ms 376 KB ok, correct split
55 Correct 2 ms 256 KB ok, correct split
56 Correct 3 ms 504 KB ok, correct split
57 Correct 4 ms 760 KB ok, correct split
58 Correct 7 ms 1272 KB ok, correct split
59 Correct 7 ms 1144 KB ok, correct split
60 Correct 7 ms 1272 KB ok, correct split
61 Correct 8 ms 1144 KB ok, correct split
62 Correct 7 ms 1192 KB ok, correct split
63 Runtime error 9 ms 2292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
64 Halted 0 ms 0 KB -