Submission #1134145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134145		steveonalex	낙하산 고리들 (IOI12_rings)	C++20	100 / 100	999 ms	133500 KiB

rings

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}

ll gcd(ll a, ll b){return __gcd(a, b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T& container, string separator = " ", string finish = "\n"){
        for(auto item: container) cout << item << separator;
        cout << finish;
    }


template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e6 + 69;
struct DSU{
    int n;
    vector<int> parent, sz, is_cycle;
    multiset<int> S;

    DSU(int _n){
        n = _n;
        parent.resize(n); sz.resize(n, 1); is_cycle.resize(n, 0);
        clear();
    }

    void clear(){
        for(int i = 0; i<n; ++i) {
            parent[i] = i;
            sz[i] = 1;
            is_cycle[i] = 0;
        }
        S.clear();
    }

    int find_set(int u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));}
    bool same_set(int u, int v){return find_set(u) == find_set(v);}

    bool join_set(int u, int v){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (sz[u] < sz[v]) swap(u, v);
            if (is_cycle[u]) S.erase(S.find(sz[u]));
            if (is_cycle[v]) S.erase(S.find(sz[v]));

            parent[v] = u;

            sz[u] += sz[v];
            is_cycle[u] |= is_cycle[v];
            if (is_cycle[u]) S.insert(sz[u]);
            return true;
        }
        if (is_cycle[u] == 0) S.insert(sz[u]);
        is_cycle[u] = 1;
        return false;
    }

    int get_size(int u){return sz[find_set(u)];}
    int get_cycle_top(){
        if (S.size() == 0) return -1;
        if (S.size() >= 2) return -2;
        return *S.begin();
    }
};

int n;
DSU mst(N);
int deg[N];
vector<int> graph[N];

int cur_ans;
int max_deg;

int banned_vertex;

void Init(int _N) {
    n = _N;
    cur_ans = n;
    max_deg = 0;
    banned_vertex = -1;
}

namespace Three{
    vector<int> hero_party;
    vector<DSU> sigma;
    vector<vector<int>> deg;
    vector<int> max_deg;
}



void Link(int u, int v) {
    if (cur_ans == 0) return;
    if (u != banned_vertex && v != banned_vertex){
        mst.join_set(u, v);
        deg[u]++;
        deg[v]++;
        graph[u].push_back(v);
        graph[v].push_back(u);
        maximize(max_deg, max(deg[u], deg[v]));
    }
    if (Three::hero_party.size() == 4){
        for(int k = 0; k < 4; ++k){
            int cur = Three::hero_party[k];
            if (u == cur || v == cur) continue;
            Three::deg[k][u]++;Three::deg[k][v]++;
            Three::sigma[k].join_set(u, v);
            maximize(Three::max_deg[k], max(Three::deg[k][u], Three::deg[k][v]));
        }
    }

    if (max_deg >= 4 && banned_vertex == -1){
        for(int i = 0; i < n; ++i) if (deg[i] >= 4) banned_vertex = i;
        mst.clear();
        for(int i = 0; i < n; ++i) for(int j: graph[i]) if (i < j){
            if (i == banned_vertex || j == banned_vertex) continue;
            mst.join_set(i, j);
        }
        for(int v: graph[banned_vertex]) {
            deg[v]--;
            deg[banned_vertex]--;
        }
        max_deg = 0;
        for(int i = 0; i < n; ++i) maximize(max_deg, deg[i]);

        cur_ans = 1;
    }
    if (banned_vertex != -1){
        if (mst.get_cycle_top() != -1 || max_deg > 2) cur_ans = 0;
        return;
    }

    int cur = mst.get_cycle_top();
    if (cur == -2) cur_ans = 0;
    else if (cur != -1){
        minimize(cur_ans, cur);
    }
    
    if (max_deg == 3){
        if (Three::hero_party.size() == 0){
            int u = -1;
            for(int i = 0; i < n; ++i) if (deg[i] == 3) u = i;

            Three::hero_party = graph[u];
            Three::hero_party.push_back(u);
            for(int i = 0; i < 4; ++i) {
                Three::sigma.push_back(DSU(n));
                Three::deg.push_back(vector<int>(n));
            }
            Three::max_deg.resize(4);

            for(int k = 0; k < 4; ++k){
                int cur = Three::hero_party[k];
                for(int i = 0; i < n; ++i) for(int j: graph[i]) if (i < j){
                    if (i == cur || j == cur) continue;
                    Three::deg[k][i]++;
                    Three::deg[k][j]++;
                    Three::sigma[k].join_set(i, j);
                    maximize(Three::max_deg[k], max(Three::deg[k][i], Three::deg[k][j]));
                }
            }
        }

        cur_ans = 0;
        for(int i = 0; i < 4; ++i){
            if (Three::max_deg[i] > 2 || Three::sigma[i].get_cycle_top() != -1) continue;
            cur_ans++;
        }
    }
}   

int CountCritical() {
    return cur_ans;
}

// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     clock_t start = clock();

//     int n, l; cin >> n >> l;
//     Init(n);
//     for(int i = 0; i < l; ++i){
//         int a; cin >> a;
//         if (a == -1) cout << CountCritical() << "\n";
//         else{
//             int b; cin >> b;
//             Link(a, b);
//         }
//     }

//     cerr << "Time elapsed: " << clock() - start << "ms!\n";
//     return 0;
// }

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