Submission #481689

#	Time	Username	Problem	Language	Result	Execution time	Memory
481689		Haruto810198	Parachute rings (IOI12_rings)	C++17	52 / 100	1853 ms	262148 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 check_id;

struct Graph{
    vi edge[MAX];
    int deg[MAX];
    int p[MAX], sz[MAX];
    int cyc, cyclen, deg3;

    void init(){
        FOR(i, 0, n-1, 1){
            edge[i].clear();
            deg[i] = 0;
            p[i] = i;
            sz[i] = 1;
        }
        cyc = 0;
        cyclen = 0;
        deg3 = 0;
    }

    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(u);
        int pv = findp(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;
    }

    void add_edge(int u, int v){
        if(u > v) swap(u, v);
        edge[u].pb(v);
        //edge[v].pb(u);
        deg[u]++;
        deg[v]++;
        if(deg[u] == 3) deg3++;
        if(deg[v] == 3) deg3++;
        if(!uni(u, v) and deg3 == 0){
            cyc++;
            cyclen = sz[findp(u)];
        }
    }
};

Graph G_now, G_check[4];

void Init(int N){
    n = N;
    G_now.init();
}

void Link(int u, int v){

    if(G_now.deg3 == 0){
        G_now.add_edge(u, v);

        if(G_now.deg3 > 0){
            if(G_now.deg[u] < G_now.deg[v]) swap(u, v);
            check_id = G_now.edge[u];
            check_id.pb(u);

            FOR(uu, 0, n-1, 1){
                for(int vv : G_now.edge[uu]){
                    if(vv == u) check_id.pb(uu);
                }
            }

            assert(szof(check_id) == 4);

            FOR(i, 0, 3, 1){
                G_check[i].init();
                FOR(uu, 0, n-1, 1){
                    if(uu == check_id[i]) continue;
                    for(int vv : G_now.edge[uu]){
                        if(vv == check_id[i]) continue;
                        G_check[i].add_edge(uu, vv);
                    }
                }
            }
        }

        return;
    }

    if(G_now.deg3 > 0){
        FOR(i, 0, 3, 1){
            if(u != check_id[i] and v != check_id[i]){
                G_check[i].add_edge(u, v);
            }
        }
    }

}

int CountCritical(){
    if(G_now.deg3 == 0){
        if(G_now.cyc == 0) return n;
        else if(G_now.cyc == 1) return G_now.cyclen;
        else return 0;
    }
    else{
        int ret = 0;
        FOR(i, 0, 3, 1){
            if(G_check[i].cyc == 0 and G_check[i].deg3 == 0) ret++;
        }
        return ret;
    }
}

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