제출 #433056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433056		someone	낙하산 고리들 (IOI12_rings)	C++14	37 / 100	2542 ms	165080 KiB

rings

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

const int N = 1e6 + 42;

struct UF {
    bool isChain = true, tree[N];
    int par[N], deg[N], diff[N], sz[N], nbCycle = 0, total = 0;

    void init(int n) {
        for(int i = 0; i < n; i++) {
            sz[i] = 1;
            par[i] = i;
            deg[i] = 0;
            diff[i] = -1;
            tree[i] = true;
        }
    }

    int F(int i) {
        if(par[i] == i)
            return i;
        return par[i] = F(par[i]);
    }

    int U(int a, int b) {
        deg[a]++;
        deg[b]++;
        int d = max(deg[a], deg[b]);
        a = F(a), b = F(b);
        if(a == b) {
            if(tree[a]) {
                total += sz[a];
                nbCycle++;
            }
            diff[a]++;
            isChain = false;
            tree[a] = false;
            return d;
        }
        if(sz[b] < sz[a])
            swap(a, b);
        par[a] = b;
        sz[b] += sz[a];
        diff[b] += diff[a] + 1;
        if(diff[b] != -1)
            isChain = false;
        if(d > 2)
            isChain = false;
        return d;
    }
};

UF uf[6];
vector<int> adj[N];
int n, maxi = 0, nbCrit, no[6];

void create(int i, int iNot) {
    no[i] = iNot;
    for(int j = 0; j <= n; j++)
        if(j != no[i])
            for(int k : adj[j])
                if(k != no[i] && j < k)
                    uf[i].U(j, k);
}

void Init(int N_) {
    n = N_;
    nbCrit = N_;
    for(int i = 0; i < 6; i++)
        uf[i].init(N_);
}

void Link(int A, int B) {
    adj[A].push_back(B);
    adj[B].push_back(A);
    int newMax = uf[0].U(A, B);
    if(maxi >= 4) {
        uf[5].U(A, B);
        if(uf[5].isChain)
            nbCrit = 1;
    } else if(maxi == 3) {
        if(newMax == 4) {
            maxi = newMax;
            int imax = 0;
            for(int i = 1; i < n; i++)
                if(adj[imax].size() < adj[i].size())
                    imax = i;
            create(5, imax);
            if(uf[5].isChain)
                nbCrit = 1;
            else
                nbCrit = 0;
        } else {
            nbCrit = 0;
            for(int i = 1; i < 5; i++) {
                if(A != no[i] && B != no[i])
                    uf[i].U(A, B);
                if(uf[i].isChain)
                    nbCrit++;
            }
        }
    } else {
        if(newMax == 3) {
            maxi = newMax;
            int imax = 0;
            for(int i = 1; i < n; i++)
                if(adj[imax].size() < adj[i].size())
                    imax = i;
            create(1, imax);
            for(int j = 0; j < 3; j++)
                create(j + 2, adj[imax][j]);
            nbCrit = 0;
            for(int i = 1; i < 5; i++)
                if(uf[i].isChain)
                    nbCrit++;
        } else {
            if(uf[0].nbCycle == 0) {
                nbCrit = n;
            } else if(uf[0].nbCycle == 1) {
                nbCrit = uf[0].total;
            } else {
                nbCrit = 0;
            }
        }
    }
}

int CountCritical() {
    return nbCrit;
}

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