제출 #760697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
760697		fatemetmhr	낙하산 고리들 (IOI12_rings)	C++17	37 / 100	1109 ms	87392 KiB

rings

//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int n;
bool found = false;
bool cy = false, morecy = false, mark[maxn5];
int cynum = 0, cnt[maxn5], q[maxn5];
vector <int> adj[maxn5];


inline void calc(){
    int l = 0, r = 0;
    memset(mark, false, sizeof mark);
    for(int i = 0; i < n; i++){
        cnt[i] = adj[i].size();
        if(cnt[i] < 2){
            mark[i] = true;
            q[r++] = i;
        }
    }
    while(l < r){
        int v = q[l++];
        for(auto u : adj[v]) if(!mark[u]){
            cnt[u]--;
            if(cnt[u] < 2){
                mark[u] = true;
                q[r++] = u;
            }
        }
    }
    cynum = 0;
    for(int i = 0; i < n; i++)
        cynum += (!mark[i]);
    memset(mark, false, sizeof mark);
}

struct _dsu{

    int remver, par[maxn5];
    bool noans;

    _dsu(){
        remver = -1;
        noans = false;
        memset(par, -1, sizeof par);
    }

    int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}

    inline void add(int a, int b){
        if(a == remver || b == remver || a == b)
            return;
        a = get_par(a);
        b = get_par(b);
        if(a == b){
            noans = true;
            if(cy)
                morecy = true;
            else{
                cy = true;
                if(remver == -1)
                    calc();
            }
            return;
        }
        if(-par[a] < -par[b])
            swap(a, b);
        par[a] += par[b];
        par[b] = a;
    }

} dsu[6];


void Init(int N_) {
    n = N_;
}

void Link(int a, int b){
    adj[a].pb(b);
    adj[b].pb(a);
    dsu[0].add(a, b);
    if(found) for(int i = 1; i < 5; i++)
        dsu[i].add(a, b);
    if(!found && adj[a].size() == 3){
        found = true;
        dsu[1].remver = a;
        for(int i = 0; i < 3; i++){
            dsu[i + 2].remver = adj[a][i];
            for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
                dsu[i + 2].add(v, u);
        }
    }
    else if(adj[a].size() == 3){
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
        for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
            dsu[i].noans = true;
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
    }
    else if(adj[a].size() == 4){
        for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
            dsu[i].noans = true;
    }
    swap(a, b);
    if(!found && adj[a].size() == 3){
        found = true;
        dsu[1].remver = a;
        for(int i = 0; i < 3; i++){
            dsu[i + 2].remver = adj[a][i];
            for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
                dsu[i + 2].add(v, u);
        }
    }
    else if(adj[a].size() == 3){
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
        for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
            dsu[i].noans = true;
        mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
    }
    else if(adj[a].size() == 4){
        for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
            dsu[i].noans = true;
    }
}

int CountCritical() {

    if(found){
        int num = 0;
        for(int i = 1; i < 5; i++) 
            num += (!dsu[i].noans);
        return num;
    }
    if(!cy)
        return n;
    if(morecy)
        return 0;
    return cynum;
}

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