Submission #760703

#	Time	Username	Problem	Language	Result	Execution time	Memory
760703		fatemetmhr	Parachute rings (IOI12_rings)	C++17	100 / 100	1006 ms	83408 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;
vector <int> adj[maxn5];
 
 
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;
        //if(remver == 3)
        //    cout << "here " << a << ' ' << b << endl;
        a = get_par(a);
        b = get_par(b);
        //if(remver == 3)
        //    cout << "and " << a << ' ' << b << endl;
        if(a == b){
            noans = true;
            if(cy)
                morecy = true;
            else{
                cy = true;
                cynum = -par[a];
            }
            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 v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
            dsu[1].add(v, u);
        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 v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
            dsu[1].add(v, u);
        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);
            //cout << i << ' ' << dsu[i].noans << ' ' << dsu[i].remver << endl;
        }
        return num;
    }
    if(!cy)
        return n;
    if(morecy)
        return 0;
    return cynum;
}

/*
4 7
1 3
1 2
2 3
0 3
0 2
0 1
-1

*/

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