Submission #481509

#	Time	Username	Problem	Language	Result	Execution time	Memory
481509		Haruto810198	낙하산 고리들 (IOI12_rings)	C++17	55 / 100	4057 ms	134156 KiB

rings

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int MAX = 1000010;

int n;
vi edge[MAX];
int deg[MAX];

int p[MAX], sz[MAX];

set<int> check;
int deg3, deg4, cycs, cyclen;

struct DSU{

    int p[MAX], sz[MAX];

    void init(){
        FOR(i, 0, n-1, 1){
            p[i] = i;
            sz[i] = 1;
        }
    }

    int findp(int v){
        if(v == p[v]) return v;
        return p[v] = findp(p[v]);
    }


    bool uni(int u, int v){
        int pu = findp(p[u]);
        int pv = findp(p[v]);
        if(pu == pv) return 0;

        if(sz[pu] >= sz[pv]){
            p[pv] = pu;
            sz[pu] += sz[pv];
        }
        else{
            p[pu] = pv;
            sz[pv] += sz[pu];
        }

        return 1;
    }

};

DSU G_now, G_check;

void Init(int N){
    n = N;
    FOR(i, 0, n-1, 1){
        check.insert(i);
    }
    G_now.init();
}

void upd_check(vi val){
    set<int> ret;
    for(int i : val){
        if(check.find(i) != check.end()) ret.insert(i);
    }
    check = ret;
}

void Link(int u, int v){
    edge[u].pb(v);
    edge[v].pb(u);
    deg[u]++;
    deg[v]++;

    if(deg[u] == 3) deg3++, upd_check({u, edge[u][0], edge[u][1], edge[u][2]});
    if(deg[v] == 3) deg3++, upd_check({v, edge[v][0], edge[v][1], edge[v][2]});
    if(deg[u] == 4) deg3--, deg4++, upd_check({u});
    if(deg[v] == 4) deg3--, deg4++, upd_check({v});

    if(deg3 + deg4 == 0 and G_now.findp(u) == G_now.findp(v)){
        G_now.uni(u, v);
        cycs++;
        cyclen += G_now.sz[G_now.findp(u)];
    }

    G_now.uni(u, v);
}

int CountCritical(){
    if(deg3 + deg4 == 0){
        if(cycs == 0) return n;
        else if(cycs == 1) return cyclen;
        else return 0;
    }
    else{
        int ret = 0;
        for(int v : check){

            bool AC = 1;
            G_check.init();

            FOR(uu, 0, n-1, 1){
                if(uu == v) continue;
                for(int vv : edge[uu]){
                    if(vv == v or uu < vv) continue;
                    if(!G_check.uni(uu, vv)) AC = 0;
                }
            }

            if(AC) ret++;
            //cerr<<"check "<<v<<": "<<AC<<endl;

        }
        return ret;
    }
}

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