oj.uz

답안 #120728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120728 2019-06-25T11:05:39 Z MAMBA 낙하산 고리들 (IOI12_rings) C++17
0 / 100
 538 ms 113616 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]); }
  bool 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;
}

Compilation message

rings.cpp: In function 'void Link(int, int, int)':
rings.cpp:47:26: warning: comparison of constant '-1' with boolean expression is always false [-Wbool-compare]
   if (ds[id].merge(A, B) == -1) can[id] = false;
       ~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 90360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 538 ms 113616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 90360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 90360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 90360 KB Output isn't correct
2 Halted 0 ms 0 KB -