oj.uz

Submission #118239

# Submission time Handle Problem Language Result Execution time Memory
118239 2019-06-18T12:08:01 Z rajarshi_basu Parachute rings (IOI12_rings) C++14
100 / 100
 3464 ms 136292 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000*100*10+10;
const int MAXVAL = 1e9+10;

int CountCritical();

// stage 1 means that all have degree atmost 2
// stage 2 means that there is degree atmost 3,
// stage 3 means that there is a node of degree 4 or higher.
int stage = 1;
int deg[MAXN];

vi g[MAXN];
vector<ii> edges;

int n;

struct DSU{
    int parent[MAXN];
    int compSize[MAXN];
    int ID = 0;
    void init(int n, bool b=0){
        //parent = new int[n];
        //if(b)compSize = new int[n];
        
        FOR(i,n)parent[i] = i;
        FOR(i,n)compSize[i] = 1;
    }
    inline int find(int a){
        if(parent[a] != a)parent[a] = find(parent[a]);
        return parent[a];
    }
    inline void merge(int a,int b){
        int pa = find(a);
        int pb = find(b);
        parent[pa] = pb;
        compSize[pb] += compSize[pa];
    }
    inline bool isSame(int a,int b){
        return find(a) == find(b);
    }
    inline int sizeOf(int a){
        return compSize[find(a)];
    }
};  

DSU dsu1;
set<int> impNodes;
DSU dsu[10];
int degindi[10][MAXN];
bool sedd[10];

vi impNd;
set<int> componentWithHighDeg;
int componentWithCycle;
bool doomed;

void Init(int N){
    doomed = false;
    n = N;//gdsu = new DSU(n);
    dsu1.init(n,1);
    componentWithCycle = -1;
}

int cntDeg;
void initStage2(int a,int b){
    impNd.clear();
    impNodes.clear();
    /*
    FOR(i,10){
        dsu[i].init(n);
        FOR(j,MAXN)degindi[i][j] = 0;
        sedd[i] = 0;
    }*/

    stage = 2;
    int ctr = 0;
    
    cntDeg = ctr;
    
    FOR(i,n){
        if(deg[i] > 2){
            impNodes.insert(i);
            for(auto e:g[i])impNodes.insert(e);

            break;
        }
    }


    for(auto e : impNodes){
        impNd.pb(e);
    }
    int xx = 0;
    for(auto x : impNd){
        dsu[xx].init(n);

        for(auto edge : edges){
            if(edge.ff == x or edge.ss == x)continue;
            degindi[xx][edge.ff]++;
            degindi[xx][edge.ss]++;
            // see if the graph has any 3deg nodes left
            if(max(degindi[xx][edge.ff],degindi[xx][edge.ss]) > 2){
                sedd[xx] = 1;
            }else{
                // check if graph has any cycles remaining
                if(dsu[xx].isSame(edge.ff,edge.ss)){
                    sedd[xx] = 1;
                }else{
                    dsu[xx].merge(edge.ff,edge.ss);
                }
            }
        }
        xx++;
    }

}

void initStage3(){
    stage = 3;
    set<int> deg4;
    dsu[9].init(n);
    FOR(i,n){
        if(deg[i] >= 4){
            deg4.insert(i);
        }
    }
    if(deg4.size() > 1){
        doomed = 1;
        return;
    }else{
        impNd.clear();
        for(auto e : deg4){
            impNd.pb(e);
        }
        int mynode = impNd[0];
        
        //cout << mynode << endl;
        for(auto e : edges){
            if(e.ff == mynode or e.ss == mynode)continue;
            degindi[9][e.ff]++;
            degindi[9][e.ss]++;
            if(degindi[9][e.ff] > 2 or degindi[9][e.ss] > 2){
                doomed = 1;
            }else if(dsu[9].isSame(e.ff,e.ss)){
                //cout << e.ff << " " << e.ss << endl;
                //cout << dsu[9].find(e.ff) << " " << dsu[9].find(e.ss) << endl;
                //cout << "MEHH" << endl;
                doomed = 1;
            }else{
                dsu[9].merge(e.ff,e.ss);
            }
        }
    }
}
bool reset = 0;

void Link(int a,int b){
    g[a].pb(b);
    g[b].pb(a);
    edges.pb({a,b});
    deg[a]++;
    deg[b]++;
    if(doomed)return;
    if(stage == 1){

        if(deg[a] > 2 or deg[b] > 2){
    //      cout << "INITING STAGE 2" << endl;
            initStage2(a,b);
        }else{
    //      cout << "PROCESSING IN STAGE 1" << endl;
            // we still have atmost degree 2
            if(dsu1.isSame(a,b)){
                // this means we are creating a cycle in this component.
                if(componentWithCycle == -1){
                    // this means this is the first component with the cycle
                    componentWithCycle = dsu1.find(a);
                }else{
                    doomed = true;
                }
            }else{
                dsu1.merge(a,b);
            }
        }
    }else if(stage == 2){
        if(deg[a] > 3 or deg[b] > 3){
    //      cout << "INITING STAGE 3" << endl;
            initStage3();
        } else {

            int xx = 0;
            
    //      cout << "PROCESSING in STAGE 2" << endl;
            for(auto x : impNd){
                if(a == x or b == x){
                    xx++;
                    continue;
                }
    //          cout << "xx : " <<  xx << endl;
                degindi[xx][a]++;
                degindi[xx][b]++;
                if(max(degindi[xx][a], degindi[xx][b]) > 2){
                    sedd[xx] = 1;
                }else{
                    if(dsu[xx].isSame(a,b)){
                        sedd[xx] = 1;
                    }else{
                        dsu[xx].merge(a,b);
                    }
                }
                xx++;
            }
        }
    }else if(stage == 3){
    //  cout << "PROCESSING STAGE 3" << endl;
        int mynode = impNd[0];
        if(deg[a] > 3 and mynode != a){
            doomed = 1;
        } else if(deg[b] > 3 and mynode != b){
            doomed = 1;
        } else {
            if(a == mynode or b == mynode)return;
            degindi[9][a]++;
            degindi[9][b]++;
            if(degindi[9][a] > 2 or degindi[9][b] > 2){
                doomed = 1;
            } else {
                if(dsu[9].isSame(a,b)){
                    doomed = 1;
                }else{
                    dsu[9].merge(a,b);
                }
            }
        }

    }

    //cout << CountCritical() << endl;
}
/*
inline bool isCritical(int x){
    DSU dsu(n);
    int deg[n];
    FOR(i,n)deg[i] = 0;

    for(auto e : edges){
        if(e.ff == x or e.ss == x)continue;
        deg[e.ff]++;
        deg[e.ss]++;
        if(dsu.find(e.ff) == dsu.find(e.ss)){

            return 0;
        }
        dsu.merge(e.ff,e.ss);
    }
    FOR(i,n)if(deg[i] > 2)return 0;
    return 1;
}*/

int CountCritical(){
    if(doomed)return 0;
    if(stage == 1 and componentWithCycle == -1){
        return n;
    }
    if(stage == 1 and componentWithCycle != -1){
        return dsu1.sizeOf(componentWithCycle);
    }
    if(stage == 2){
        int ctr = 0;
        FOR(i,impNd.size()){
            ctr += !sedd[i];
        }
        return ctr;
    }

    //while(1);
    return 1;
}

int ma1in(){
    Init(10);
    //cout << CountCritical() << endl;
    Link(0,1);
    Link(1,2);
    
    Link(3,4);
    Link(3,5);
    Link(4,5);
    Link(2,0);

    //Link(2,3);
    //Link(2,4);
    /*
    Link(4,5);
    Link(5,6);
    Link(4,6);
    */
    return 0;
}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:17:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,n) for(int i=0;i<n;i++)
rings.cpp:303:13:
         FOR(i,impNd.size()){
             ~~~~~~~~~~~~~~     
rings.cpp:303:9: note: in expansion of macro 'FOR'
         FOR(i,impNd.size()){
         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB Output is correct
2 Correct 26 ms 24448 KB Output is correct
3 Correct 26 ms 24568 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 26 ms 24320 KB Output is correct
7 Correct 23 ms 24320 KB Output is correct
8 Correct 25 ms 24164 KB Output is correct
9 Correct 25 ms 24576 KB Output is correct
10 Correct 25 ms 24576 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 51108 KB Output is correct
2 Correct 1714 ms 112348 KB Output is correct
3 Correct 1206 ms 129580 KB Output is correct
4 Correct 1645 ms 75408 KB Output is correct
5 Correct 1673 ms 75616 KB Output is correct
6 Correct 1538 ms 74068 KB Output is correct
7 Correct 1200 ms 128640 KB Output is correct
8 Correct 3283 ms 116140 KB Output is correct
9 Correct 3464 ms 122128 KB Output is correct
10 Correct 996 ms 73168 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB Output is correct
2 Correct 26 ms 24448 KB Output is correct
3 Correct 26 ms 24568 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 26 ms 24320 KB Output is correct
7 Correct 23 ms 24320 KB Output is correct
8 Correct 25 ms 24164 KB Output is correct
9 Correct 25 ms 24576 KB Output is correct
10 Correct 25 ms 24576 KB Output is correct
11 Correct 25 ms 24576 KB Output is correct
12 Correct 30 ms 25208 KB Output is correct
13 Correct 30 ms 25216 KB Output is correct
14 Correct 28 ms 25080 KB Output is correct
15 Correct 29 ms 25472 KB Output is correct
16 Correct 32 ms 24696 KB Output is correct
17 Correct 30 ms 25152 KB Output is correct
18 Correct 30 ms 26108 KB Output is correct
19 Correct 28 ms 24568 KB Output is correct
20 Correct 29 ms 25208 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB Output is correct
2 Correct 26 ms 24448 KB Output is correct
3 Correct 26 ms 24568 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 26 ms 24320 KB Output is correct
7 Correct 23 ms 24320 KB Output is correct
8 Correct 25 ms 24164 KB Output is correct
9 Correct 25 ms 24576 KB Output is correct
10 Correct 25 ms 24576 KB Output is correct
11 Correct 25 ms 24576 KB Output is correct
12 Correct 30 ms 25208 KB Output is correct
13 Correct 30 ms 25216 KB Output is correct
14 Correct 28 ms 25080 KB Output is correct
15 Correct 29 ms 25472 KB Output is correct
16 Correct 32 ms 24696 KB Output is correct
17 Correct 30 ms 25152 KB Output is correct
18 Correct 30 ms 26108 KB Output is correct
19 Correct 28 ms 24568 KB Output is correct
20 Correct 29 ms 25208 KB Output is correct
21 Correct 42 ms 26280 KB Output is correct
22 Correct 57 ms 27412 KB Output is correct
23 Correct 72 ms 28348 KB Output is correct
24 Correct 80 ms 31984 KB Output is correct
25 Correct 39 ms 30456 KB Output is correct
26 Correct 83 ms 34160 KB Output is correct
27 Correct 88 ms 29428 KB Output is correct
28 Correct 119 ms 33640 KB Output is correct
29 Correct 71 ms 33524 KB Output is correct
30 Correct 101 ms 30176 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23928 KB Output is correct
2 Correct 26 ms 24448 KB Output is correct
3 Correct 26 ms 24568 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 26 ms 24320 KB Output is correct
7 Correct 23 ms 24320 KB Output is correct
8 Correct 25 ms 24164 KB Output is correct
9 Correct 25 ms 24576 KB Output is correct
10 Correct 25 ms 24576 KB Output is correct
11 Correct 541 ms 51108 KB Output is correct
12 Correct 1714 ms 112348 KB Output is correct
13 Correct 1206 ms 129580 KB Output is correct
14 Correct 1645 ms 75408 KB Output is correct
15 Correct 1673 ms 75616 KB Output is correct
16 Correct 1538 ms 74068 KB Output is correct
17 Correct 1200 ms 128640 KB Output is correct
18 Correct 3283 ms 116140 KB Output is correct
19 Correct 3464 ms 122128 KB Output is correct
20 Correct 996 ms 73168 KB Output is correct
21 Correct 25 ms 24576 KB Output is correct
22 Correct 30 ms 25208 KB Output is correct
23 Correct 30 ms 25216 KB Output is correct
24 Correct 28 ms 25080 KB Output is correct
25 Correct 29 ms 25472 KB Output is correct
26 Correct 32 ms 24696 KB Output is correct
27 Correct 30 ms 25152 KB Output is correct
28 Correct 30 ms 26108 KB Output is correct
29 Correct 28 ms 24568 KB Output is correct
30 Correct 29 ms 25208 KB Output is correct
31 Correct 42 ms 26280 KB Output is correct
32 Correct 57 ms 27412 KB Output is correct
33 Correct 72 ms 28348 KB Output is correct
34 Correct 80 ms 31984 KB Output is correct
35 Correct 39 ms 30456 KB Output is correct
36 Correct 83 ms 34160 KB Output is correct
37 Correct 88 ms 29428 KB Output is correct
38 Correct 119 ms 33640 KB Output is correct
39 Correct 71 ms 33524 KB Output is correct
40 Correct 101 ms 30176 KB Output is correct
41 Correct 273 ms 43672 KB Output is correct
42 Correct 1117 ms 99392 KB Output is correct
43 Correct 305 ms 83888 KB Output is correct
44 Correct 820 ms 136292 KB Output is correct
45 Correct 1239 ms 129404 KB Output is correct
46 Correct 952 ms 78240 KB Output is correct
47 Correct 1444 ms 79208 KB Output is correct
48 Correct 634 ms 119772 KB Output is correct
49 Correct 904 ms 77400 KB Output is correct
50 Correct 1046 ms 76740 KB Output is correct
51 Correct 377 ms 88168 KB Output is correct
52 Correct 1764 ms 106084 KB Output is correct
53 Correct 676 ms 120420 KB Output is correct
54 Correct 2833 ms 114528 KB Output is correct
55 Correct 1537 ms 132748 KB Output is correct