oj.uz

Submission #118226

# Submission time Handle Problem Language Result Execution time Memory
118226 2019-06-18T11:52:36 Z rajarshi_basu Parachute rings (IOI12_rings) C++14
37 / 100
 3367 ms 141792 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[5];
int degindi[5][MAXN];
bool sedd[5];

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;
    if(ctr <= 2){
        // all the neighbours are also important too
        FOR(i,n){
            if(deg[i] > 2){
                impNodes.insert(i);
                for(auto e:g[i])impNodes.insert(e);

                break;
            }
        }
    }else{
        FOR(i,n){
            if(deg[i] > 2){
                impNodes.insert(i);
            }
        }
    }
    for(auto e : impNodes){
        impNd.pb(e);
    }
    int xx = 0;
    for(auto x : impNd){
        dsu[xx].init(n);
        //cout << "xx : " <<  xx << endl;
        sedd[xx] = 0;
        FOR(j,MAXN)degindi[xx][j] = 0;
        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(){
    set<int> deg4;
    dsu[4].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[4][e.ff]++;
            degindi[4][e.ss]++;
            if(dsu[4].isSame(e.ff,e.ss)){
                //cout << e.ff << " " << e.ss << endl;
                //cout << dsu[4].find(e.ff) << " " << dsu[4].find(e.ss) << endl;
                //cout << "MEHH" << endl;
                doomed = 1;
            }else{
                dsu[4].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[4][a]++;
            degindi[4][b]++;
            if(degindi[4][a] > 2 or degindi[4][b] > 2){
                doomed = 1;
            } else {
                if(dsu[4].isSame(a,b)){
                    doomed = 1;
                }else{
                    dsu[4].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:308:13:
         FOR(i,impNd.size()){
             ~~~~~~~~~~~~~~     
rings.cpp:308: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 22 ms 23928 KB Output is correct
2 Correct 36 ms 40056 KB Output is correct
3 Correct 37 ms 40184 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 22 ms 24028 KB Output is correct
6 Correct 23 ms 24192 KB Output is correct
7 Correct 33 ms 39800 KB Output is correct
8 Correct 23 ms 24192 KB Output is correct
9 Correct 36 ms 40056 KB Output is correct
10 Correct 37 ms 40040 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 57248 KB Output is correct
2 Correct 2594 ms 125552 KB Output is correct
3 Correct 1236 ms 141792 KB Output is correct
4 Correct 1623 ms 88292 KB Output is correct
5 Correct 1612 ms 88468 KB Output is correct
6 Correct 1558 ms 86612 KB Output is correct
7 Correct 1156 ms 140356 KB Output is correct
8 Correct 3175 ms 129124 KB Output is correct
9 Correct 3367 ms 135060 KB Output is correct
10 Correct 985 ms 85352 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 36 ms 40056 KB Output is correct
3 Correct 37 ms 40184 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 22 ms 24028 KB Output is correct
6 Correct 23 ms 24192 KB Output is correct
7 Correct 33 ms 39800 KB Output is correct
8 Correct 23 ms 24192 KB Output is correct
9 Correct 36 ms 40056 KB Output is correct
10 Correct 37 ms 40040 KB Output is correct
11 Correct 37 ms 40184 KB Output is correct
12 Correct 40 ms 40696 KB Output is correct
13 Incorrect 41 ms 40696 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 36 ms 40056 KB Output is correct
3 Correct 37 ms 40184 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 22 ms 24028 KB Output is correct
6 Correct 23 ms 24192 KB Output is correct
7 Correct 33 ms 39800 KB Output is correct
8 Correct 23 ms 24192 KB Output is correct
9 Correct 36 ms 40056 KB Output is correct
10 Correct 37 ms 40040 KB Output is correct
11 Correct 37 ms 40184 KB Output is correct
12 Correct 40 ms 40696 KB Output is correct
13 Incorrect 41 ms 40696 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23928 KB Output is correct
2 Correct 36 ms 40056 KB Output is correct
3 Correct 37 ms 40184 KB Output is correct
4 Correct 21 ms 23936 KB Output is correct
5 Correct 22 ms 24028 KB Output is correct
6 Correct 23 ms 24192 KB Output is correct
7 Correct 33 ms 39800 KB Output is correct
8 Correct 23 ms 24192 KB Output is correct
9 Correct 36 ms 40056 KB Output is correct
10 Correct 37 ms 40040 KB Output is correct
11 Correct 545 ms 57248 KB Output is correct
12 Correct 2594 ms 125552 KB Output is correct
13 Correct 1236 ms 141792 KB Output is correct
14 Correct 1623 ms 88292 KB Output is correct
15 Correct 1612 ms 88468 KB Output is correct
16 Correct 1558 ms 86612 KB Output is correct
17 Correct 1156 ms 140356 KB Output is correct
18 Correct 3175 ms 129124 KB Output is correct
19 Correct 3367 ms 135060 KB Output is correct
20 Correct 985 ms 85352 KB Output is correct
21 Correct 37 ms 40184 KB Output is correct
22 Correct 40 ms 40696 KB Output is correct
23 Incorrect 41 ms 40696 KB Output isn't correct
24 Halted 0 ms 0 KB -