제출 #69603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69603		funcsr	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1611 ms	115812 KiB

rings

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;

struct UF {
  int U[1000000], R[1000000];
  void init(int N) {
    rep(i, N) U[i]=i, R[i]=1;
  }
  int find(int x) {
    if (U[x]==x)return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x=find(x), y=find(y);
    if(x==y)return;
    if (R[x]<R[y])swap(x,y);
    U[y]=x;
    R[x]+=R[y];
  }
  bool same(int x, int y) {
    return find(x)==find(y);
  }
};

int N;
struct Tree {
  UF uf;
  int X;
  bool dead;
  Tree() {}
  Tree(int X, vector<P> edges) : X(X), dead(false) {
    uf.init(N);
    for (P p : edges) add_edge(p._1, p._2);
  }
  void add_edge(int a, int b) {
    if (dead) return;
    if (a==X||b==X) return;
    if (uf.same(a, b)) dead = true;
    uf.unite(a, b);
  }
};


vector<int> G[1000000];
UF uf;
bool deg012 = true;
vector<int> cycles;
Tree cand[4];
vector<P> edges;

void cand_filter(vector<int> seq) {
  rep(i, 4) if (!cand[i].dead) {
    bool ok = false;
    for (int x : seq) if (x == cand[i].X) ok = true;
    if (!ok) cand[i].dead = true;
  }
}

void Init(int N_) {
  N = N_;
  uf.init(N);
}

void Link(int a, int b) {
  edges.pb(P(a, b));
  G[a].pb(b);
  G[b].pb(a);
  if (!deg012) rep(i, 4) cand[i].add_edge(a, b);

  if (G[a].size() < 3) swap(a, b);
  if (deg012 && G[a].size() >= 3) {
    deg012 = false;
    cand[0] = Tree(a, edges);
    cand[1] = Tree(G[a][0], edges);
    cand[2] = Tree(G[a][1], edges);
    cand[3] = Tree(G[a][2], edges);
  }
  if (G[a].size() == 3) cand_filter({a, G[a][0], G[a][1], G[a][2]});
  if (G[b].size() == 3) cand_filter({b, G[b][0], G[b][1], G[b][2]});
  if (G[a].size() >= 4) cand_filter({a});
  if (G[b].size() >= 4) cand_filter({b});

  if (deg012 && cycles.size() <= 1) {
    bool same = uf.same(a, b);
    uf.unite(a, b);
    if (same) cycles.pb(uf.R[uf.find(a)]);
  }
}

int CountCritical() {
  if (deg012) {
    if (cycles.size() == 0) return N;
    else if (cycles.size() == 1) return cycles[0];
    else return 0;
  }
  else {
    int s = 0;
    rep(i, 4) s += !cand[i].dead;
    return s;
  }
}

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