제출 #427702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427702		MarcoMeijer	낙하산 고리들 (IOI12_rings)	C++14	0 / 100	2713 ms	188536 KiB

rings

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), e.end()

const int MX = 1e6+10;

int n;

struct DSU {
  int p[MX], r[MX], sz[MX], e[MX][2];
  int cnt[MX];
  int bigCnt = 0, smallCnt = 0;
  int cycles = 0, cycleLength = 0;
  void build() {
    RE(i,n) p[i] = i, r[i]=0, e[i][0]=e[i][1]=i, sz[i] = 1;
    RE(i,n) cnt[i] = 0;
  }
  int getSet(int x) {return x==p[x] ? x : p[x]=getSet(p[x]);}
  void link(int x, int y) {
    cnt[x]++;
    cnt[y]++;
    if(cnt[x] == 4) bigCnt++;
    if(cnt[y] == 4) bigCnt++;
    if(cnt[x] == 3) smallCnt++;
    if(cnt[y] == 3) smallCnt++;
    int u = getSet(x), v = getSet(y);
    if((e[u][0] == x && e[u][1] == y) || (e[u][0] == y && e[u][1] == x)) {
      cycles++;
      cycleLength = sz[u];
      return;
    }
    if(u != v) {
      sz[u] = sz[v] = sz[u] + sz[v];
      int i = 0, j = 0;
      if(e[u][0] != y) i = 1;
      if(e[v][0] != x) j = 1;
      e[u][i] = e[v][!j];
      RE(i,2) e[v][i] = e[u][i];
      if(r[u] > r[v]) {
        p[v] = u;
      } else {
        p[u] = v;
        if(r[u] == r[v]) r[v]++;
      }
    }
  }
};

DSU g;
vi adj[MX];
vii opperations;
bool started = false;
DSU other[4]; int ign[4];

void Init(int N_) {
  n = N_;
  g.build();
}

void createGraph(int i) {
  other[i].build();
  FOR(p,opperations) {
    int A = p.fi, B = p.se;
    if(A == ign[i] || B == ign[i])
      continue;
    other[i].link(A,B);
  }
}
void Link(int A, int B) {
  adj[A].pb(B);
  adj[B].pb(A);
  opperations.pb({A,B});
  g.link(A,B);
  if(started) {
    RE(i,4) {
      if(A == ign[i] || B == ign[i])
        continue;
      other[i].link(A,B);
    }
  }
  else if(adj[A].size() == 3 || adj[B].size() == 3) {
    int u = A;
    if(adj[B].size() == 3) u = B;
    ign[0] = u; int i=0;
    FOR(v,adj[u]) ign[++i] = v;
    RE(i,4) createGraph(i);
    started = true;
  }
}

int CountCritical() {
  if(g.bigCnt >= 2)
    return 0;
  if(started) {
    int cnt = 0;
    RE(i,4)
      if(other[i].cycles == 0 && other[i].smallCnt == 0)
        cnt++;
    return cnt;
  }
  if(g.cycles == 0)
    return n;
  if(g.cycles >= 2)
    return 0;
  return g.cycleLength;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31