제출 #569797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569797		definitelynotmee	낙하산 고리들 (IOI12_rings)	C++98	100 / 100	2283 ms	236328 KiB

rings

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
using namespace std;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const double EPS = 1e-7;
const int MOD = 1e9 + 7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

struct UnionFind{
    bool good = 1;
    int root;
    vector<int> pai, degree;

    UnionFind(int n = 0, int start = 0){
        root = start;
        pai = vector<int>(n+1);
        iota(all(pai),0);
        degree = vector<int>(n+1);
    }
    int find (int id){
        if(pai[id] == id)
            return id;
        return pai[id] = find(pai[id]);
    }
    void onion(int a, int b){

        if(a == root || b == root)
            return;
        //cout << root << " push(" << a << ',' << b << ")\n";
        degree[a]++;
        degree[b]++;
        if(degree[a] == 3)
            good = 0;//, cout << "=>" << root << " bad " << a <<  "\n";
        if(degree[b] == 3)
            good = 0;//, cout << "=>" << root << " bad " << b <<  "\n";
        a = find(a), b = find(b);
        if(a!=b){
            pai[b] = a;
        } else {
            good = 0;//, cout << "=>" << root << " badc\n";
        }
    }
};

struct UnionFind2{
    int cycle = -1;
    int cyclect = 0;
    vector<int> pai, sizee;

    UnionFind2(int n = 0){
        pai = vector<int>(n+1);
        sizee = vector<int> (n+1,1);
        iota(all(pai),0);
    }
    int find (int id){
        if(pai[id] == id)
            return id;
        return pai[id] = find(pai[id]);
    }
    void onion(int a, int b){
        a = find(a), b = find(b);
        if(a == b){
            cycle = a;
            cyclect++;
        } else{
            sizee[a] += sizee[b];
            pai[b] = a;
        }
    }
} ufsmall;

int n;

matrix<int> g;
vector<int> cand;
vector<UnionFind> uf;

int mode = 0;
int mode2big;

void inituf(int x, int y){
    if(mode < 2)
    for(int i : g[x]){
        if(cand[i]!=-1)
            continue;
        cand[i] = uf.size();
        uf.push_back(UnionFind(n,i));
        for(int j = 0; j < n; j++){
            for(int k : g[j]){
                if(j > k)
                    continue;
                int a = j , b = k;
                if(!(a == min(x,y) && b == max(x,y)))
                    uf.back().onion(j,k);
            }
        }
    }
    if(cand[x]==-1){
        cand[x] = uf.size();
        uf.push_back(UnionFind(n,x));
        for(int j = 0; j < n; j++){
            for(int k : g[j]){
                if(j > k)
                    continue;
                int a = j , b = k;
                if(!(a == min(x,y) && b == max(x,y)))
                    uf.back().onion(j,k);
            }
        }
    }

}


void Init(int N_) {

  n = N_;
  g = matrix<int>(n+1);
  cand = vector<int>(n+1,-1);
  ufsmall = UnionFind2(n);
}

void Link(int A, int B) {
    if(mode == 3)
        return;
    g[A].push_back(B);
    g[B].push_back(A);
    if(g[A].size() == 4){
        if(mode == 2){
            mode = 3;
            return;
        }else mode2big = A, mode = 2, uf.clear(), fill(all(cand),-1), inituf(A,B);
    }
    if(g[B].size() == 4){
        if(mode == 2){
            mode = 3;
            return;
        }else mode2big = B, mode = 2, uf.clear(), fill(all(cand),-1), inituf(B,A);
    }
    if(g[A].size() == 3 && mode < 2){
        mode = 1;
        inituf(A,B);
    }
    if(g[B].size() == 3 && mode < 2){
        mode = 1;
        inituf(B,A);
    }
    if(mode == 0){
        ufsmall.onion(A,B);
        if(ufsmall.cyclect >= 2)
            mode = 3;
    }
    if(uf.size() > 20){
        mode = 3;
        return;
    }
    for(auto& i : uf){
        i.onion(A,B);
    }

}

int CountCritical() {
    if(mode == 3)
        return 0;
    if(mode == 0){
        if(ufsmall.cyclect == 0)
            return n;
        assert(ufsmall.cycle >= 0);
        return ufsmall.sizee[ufsmall.cycle];
    }
    int resp =0;
    for(auto& i : uf){
        //cout << "->" << i.root << ' ' << i.good << '\n';
        resp+=i.good;
    }

    return resp;
}

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