oj.uz

Submission #120739

# Submission time Handle Problem Language Result Execution time Memory
120739 2019-06-25T11:13:26 Z MAMBA Parachute rings (IOI12_rings) C++17
100 / 100
 3928 ms 131688 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back

constexpr int MAXN = 1e6 + 10;

struct dsu {
  int par[MAXN], sz[MAXN];
  dsu() {
    iota(par, par + MAXN, 0);
    fill(sz, sz + MAXN, 1);
  }
  int getPar(int v) { return par[v] == v ? v : par[v] = getPar(par[v]); }
  int merge(int u, int v) {
    v = getPar(v), u = getPar(u);
    if (v == u) return sz[v];
    par[v] = u;
    sz[u] += sz[v];
    return -1;
  }
} ds[5];

int N, tmp, deg[5][MAXN];
vector<int> adj[MAXN];
bool flag, can[5];

void Init(int N_) {
  N = N_;
  tmp = 0;
  flag = false;
  memset(can, true, sizeof(can));
  memset(deg, 0, sizeof(deg));
  rep(i, 0, 5) ds[i] = dsu();
  rep(i, 0, N) adj[i].clear();
}

int bad[5];

inline void Link(int A, int B, int id) {
  if (bad[id] == A || bad[id] == B) return;
  deg[id][A]++, deg[id][B]++;
  if (deg[id][A] == 3 || deg[id][B] == 3) can[id] = false;
  if (~ds[id].merge(A, B)) can[id] = false;
}

inline void build(int v) {
  flag = true;
  bad[1] = v;
  rep(i, 0, 3) bad[2 + i] = adj[v][i];
  rep(i, 0, N) for (auto e : adj[i]) if (e > i) rep(z, 1, 5) Link(i, e, z);
}

void Link(int A, int B) {
  adj[A].pb(B);
  adj[B].pb(A);
  if (!flag && adj[A].size() == 3) return build(A), void();
  if (!flag && adj[B].size() == 3) return build(B), void();
  if (!flag) {
    int me = ds[0].merge(A, B);
    if (~me) {
      if (!tmp)
        tmp = me;
      else
        tmp = -1;
    }
  } else
    rep(i, 1, 5) Link(A, B, i);
}

int CountCritical() {
  if (!flag) {
    if (!tmp) return N;
    if (~tmp) return tmp;
    return 0;
  }
  int res = 0;
  rep(i, 1, 5) res += can[i];
  return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 90448 KB Output is correct
2 Correct 90 ms 90488 KB Output is correct
3 Correct 93 ms 90616 KB Output is correct
4 Correct 88 ms 90360 KB Output is correct
5 Correct 98 ms 90536 KB Output is correct
6 Correct 91 ms 90488 KB Output is correct
7 Correct 89 ms 90332 KB Output is correct
8 Correct 90 ms 90488 KB Output is correct
9 Correct 89 ms 90616 KB Output is correct
10 Correct 91 ms 90616 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 106672 KB Output is correct
2 Correct 3113 ms 115492 KB Output is correct
3 Correct 3928 ms 127524 KB Output is correct
4 Correct 1537 ms 131688 KB Output is correct
5 Correct 1504 ms 131672 KB Output is correct
6 Correct 1562 ms 130548 KB Output is correct
7 Correct 3926 ms 127352 KB Output is correct
8 Correct 3628 ms 129632 KB Output is correct
9 Correct 3647 ms 131676 KB Output is correct
10 Correct 975 ms 130044 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 90448 KB Output is correct
2 Correct 90 ms 90488 KB Output is correct
3 Correct 93 ms 90616 KB Output is correct
4 Correct 88 ms 90360 KB Output is correct
5 Correct 98 ms 90536 KB Output is correct
6 Correct 91 ms 90488 KB Output is correct
7 Correct 89 ms 90332 KB Output is correct
8 Correct 90 ms 90488 KB Output is correct
9 Correct 89 ms 90616 KB Output is correct
10 Correct 91 ms 90616 KB Output is correct
11 Correct 90 ms 90680 KB Output is correct
12 Correct 89 ms 90744 KB Output is correct
13 Correct 92 ms 90744 KB Output is correct
14 Correct 89 ms 90620 KB Output is correct
15 Correct 93 ms 90732 KB Output is correct
16 Correct 89 ms 90744 KB Output is correct
17 Correct 90 ms 90872 KB Output is correct
18 Correct 91 ms 90872 KB Output is correct
19 Correct 89 ms 90784 KB Output is correct
20 Correct 89 ms 90872 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 90448 KB Output is correct
2 Correct 90 ms 90488 KB Output is correct
3 Correct 93 ms 90616 KB Output is correct
4 Correct 88 ms 90360 KB Output is correct
5 Correct 98 ms 90536 KB Output is correct
6 Correct 91 ms 90488 KB Output is correct
7 Correct 89 ms 90332 KB Output is correct
8 Correct 90 ms 90488 KB Output is correct
9 Correct 89 ms 90616 KB Output is correct
10 Correct 91 ms 90616 KB Output is correct
11 Correct 90 ms 90680 KB Output is correct
12 Correct 89 ms 90744 KB Output is correct
13 Correct 92 ms 90744 KB Output is correct
14 Correct 89 ms 90620 KB Output is correct
15 Correct 93 ms 90732 KB Output is correct
16 Correct 89 ms 90744 KB Output is correct
17 Correct 90 ms 90872 KB Output is correct
18 Correct 91 ms 90872 KB Output is correct
19 Correct 89 ms 90784 KB Output is correct
20 Correct 89 ms 90872 KB Output is correct
21 Correct 102 ms 91764 KB Output is correct
22 Correct 119 ms 92656 KB Output is correct
23 Correct 130 ms 93176 KB Output is correct
24 Correct 166 ms 92792 KB Output is correct
25 Correct 104 ms 90872 KB Output is correct
26 Correct 149 ms 93304 KB Output is correct
27 Correct 145 ms 94168 KB Output is correct
28 Correct 178 ms 94252 KB Output is correct
29 Correct 139 ms 92604 KB Output is correct
30 Correct 173 ms 94604 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 90448 KB Output is correct
2 Correct 90 ms 90488 KB Output is correct
3 Correct 93 ms 90616 KB Output is correct
4 Correct 88 ms 90360 KB Output is correct
5 Correct 98 ms 90536 KB Output is correct
6 Correct 91 ms 90488 KB Output is correct
7 Correct 89 ms 90332 KB Output is correct
8 Correct 90 ms 90488 KB Output is correct
9 Correct 89 ms 90616 KB Output is correct
10 Correct 91 ms 90616 KB Output is correct
11 Correct 560 ms 106672 KB Output is correct
12 Correct 3113 ms 115492 KB Output is correct
13 Correct 3928 ms 127524 KB Output is correct
14 Correct 1537 ms 131688 KB Output is correct
15 Correct 1504 ms 131672 KB Output is correct
16 Correct 1562 ms 130548 KB Output is correct
17 Correct 3926 ms 127352 KB Output is correct
18 Correct 3628 ms 129632 KB Output is correct
19 Correct 3647 ms 131676 KB Output is correct
20 Correct 975 ms 130044 KB Output is correct
21 Correct 90 ms 90680 KB Output is correct
22 Correct 89 ms 90744 KB Output is correct
23 Correct 92 ms 90744 KB Output is correct
24 Correct 89 ms 90620 KB Output is correct
25 Correct 93 ms 90732 KB Output is correct
26 Correct 89 ms 90744 KB Output is correct
27 Correct 90 ms 90872 KB Output is correct
28 Correct 91 ms 90872 KB Output is correct
29 Correct 89 ms 90784 KB Output is correct
30 Correct 89 ms 90872 KB Output is correct
31 Correct 102 ms 91764 KB Output is correct
32 Correct 119 ms 92656 KB Output is correct
33 Correct 130 ms 93176 KB Output is correct
34 Correct 166 ms 92792 KB Output is correct
35 Correct 104 ms 90872 KB Output is correct
36 Correct 149 ms 93304 KB Output is correct
37 Correct 145 ms 94168 KB Output is correct
38 Correct 178 ms 94252 KB Output is correct
39 Correct 139 ms 92604 KB Output is correct
40 Correct 173 ms 94604 KB Output is correct
41 Correct 331 ms 102424 KB Output is correct
42 Correct 1479 ms 113348 KB Output is correct
43 Correct 478 ms 97528 KB Output is correct
44 Correct 1730 ms 130748 KB Output is correct
45 Correct 3057 ms 120836 KB Output is correct
46 Correct 917 ms 128864 KB Output is correct
47 Correct 1258 ms 129376 KB Output is correct
48 Correct 1455 ms 113596 KB Output is correct
49 Correct 851 ms 126460 KB Output is correct
50 Correct 938 ms 126072 KB Output is correct
51 Correct 691 ms 99576 KB Output is correct
52 Correct 1541 ms 123812 KB Output is correct
53 Correct 1518 ms 113832 KB Output is correct
54 Correct 3029 ms 127796 KB Output is correct
55 Correct 3762 ms 130536 KB Output is correct