oj.uz

Submission #120730

# Submission time Handle Problem Language Result Execution time Memory
120730 2019-06-25T11:06:12 Z MAMBA Parachute rings (IOI12_rings) C++17
0 / 100
 2786 ms 125644 KB 
#include <bits/stdc++.h>
//#include "grader.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) == -1) can[id] = false;
}

inline void build(int v) {
  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 (adj[A].size() == 3) {
    flag = true;
    build(A);
  } else if (adj[B].size() == 3) {
    flag = true;
    build(B);
  }
  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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 90332 KB Output is correct
2 Incorrect 86 ms 90608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 106736 KB Output is correct
2 Incorrect 2786 ms 125644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 90332 KB Output is correct
2 Incorrect 86 ms 90608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 90332 KB Output is correct
2 Incorrect 86 ms 90608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 90332 KB Output is correct
2 Incorrect 86 ms 90608 KB Output isn't correct
3 Halted 0 ms 0 KB -