oj.uz

Submission #118231

# Submission time Handle Problem Language Result Execution time Memory
118231 2019-06-18T11:55:45 Z rajarshi_basu Parachute rings (IOI12_rings) C++14
37 / 100
 3449 ms 129336 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(){
    stage = 3;
    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:309:13:
         FOR(i,impNd.size()){
             ~~~~~~~~~~~~~~     
rings.cpp:309: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 24 ms 23928 KB Output is correct
2 Correct 39 ms 40064 KB Output is correct
3 Correct 40 ms 40056 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 33 ms 24184 KB Output is correct
7 Correct 37 ms 39800 KB Output is correct
8 Correct 33 ms 24056 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct
10 Correct 39 ms 40060 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 50596 KB Output is correct
2 Correct 1868 ms 114992 KB Output is correct
3 Correct 1262 ms 129336 KB Output is correct
4 Correct 1663 ms 74960 KB Output is correct
5 Correct 1620 ms 75156 KB Output is correct
6 Correct 1555 ms 73984 KB Output is correct
7 Correct 1186 ms 128340 KB Output is correct
8 Correct 3141 ms 116700 KB Output is correct
9 Correct 3449 ms 121808 KB Output is correct
10 Correct 1010 ms 72564 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 39 ms 40064 KB Output is correct
3 Correct 40 ms 40056 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 33 ms 24184 KB Output is correct
7 Correct 37 ms 39800 KB Output is correct
8 Correct 33 ms 24056 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct
10 Correct 39 ms 40060 KB Output is correct
11 Correct 39 ms 40104 KB Output is correct
12 Correct 42 ms 40568 KB Output is correct
13 Correct 40 ms 40576 KB Output is correct
14 Correct 44 ms 40568 KB Output is correct
15 Correct 45 ms 40928 KB Output is correct
16 Correct 31 ms 24516 KB Output is correct
17 Correct 42 ms 40508 KB Output is correct
18 Incorrect 82 ms 41336 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 39 ms 40064 KB Output is correct
3 Correct 40 ms 40056 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 33 ms 24184 KB Output is correct
7 Correct 37 ms 39800 KB Output is correct
8 Correct 33 ms 24056 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct
10 Correct 39 ms 40060 KB Output is correct
11 Correct 39 ms 40104 KB Output is correct
12 Correct 42 ms 40568 KB Output is correct
13 Correct 40 ms 40576 KB Output is correct
14 Correct 44 ms 40568 KB Output is correct
15 Correct 45 ms 40928 KB Output is correct
16 Correct 31 ms 24516 KB Output is correct
17 Correct 42 ms 40508 KB Output is correct
18 Incorrect 82 ms 41336 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 39 ms 40064 KB Output is correct
3 Correct 40 ms 40056 KB Output is correct
4 Correct 23 ms 23936 KB Output is correct
5 Correct 24 ms 24064 KB Output is correct
6 Correct 33 ms 24184 KB Output is correct
7 Correct 37 ms 39800 KB Output is correct
8 Correct 33 ms 24056 KB Output is correct
9 Correct 39 ms 40056 KB Output is correct
10 Correct 39 ms 40060 KB Output is correct
11 Correct 556 ms 50596 KB Output is correct
12 Correct 1868 ms 114992 KB Output is correct
13 Correct 1262 ms 129336 KB Output is correct
14 Correct 1663 ms 74960 KB Output is correct
15 Correct 1620 ms 75156 KB Output is correct
16 Correct 1555 ms 73984 KB Output is correct
17 Correct 1186 ms 128340 KB Output is correct
18 Correct 3141 ms 116700 KB Output is correct
19 Correct 3449 ms 121808 KB Output is correct
20 Correct 1010 ms 72564 KB Output is correct
21 Correct 39 ms 40104 KB Output is correct
22 Correct 42 ms 40568 KB Output is correct
23 Correct 40 ms 40576 KB Output is correct
24 Correct 44 ms 40568 KB Output is correct
25 Correct 45 ms 40928 KB Output is correct
26 Correct 31 ms 24516 KB Output is correct
27 Correct 42 ms 40508 KB Output is correct
28 Incorrect 82 ms 41336 KB Output isn't correct
29 Halted 0 ms 0 KB -