Submission #280334

#	Time	Username	Problem	Language	Result	Execution time	Memory
280334		eohomegrownapps	Parachute rings (IOI12_rings)	C++14	100 / 100	2124 ms	152404 KiB

rings

#include <bits/stdc++.h>
using namespace std;

int n;

struct UFDS{
    int n;
    vector<int> parent;
    vector<int> edges;
    vector<int> vertices;
    vector<int> vcnt;
    int numCycles = 0;
    int cycleVertices = 0;
    bool isLinear;

    UFDS(int _n){
        n=_n;
        parent.resize(n);
        edges.resize(n,0);
        vertices.resize(n,1);
        vcnt.resize(n,0);
        isLinear = true;
        for (int i = 0; i<n; i++){
            parent[i]=i;
        }
    }

    int root(int x){
        if (x==parent[x]){return x;}
        return parent[x]=root(parent[x]);
    }

    void connect(int a, int b){
        vcnt[a]++;
        vcnt[b]++;
        if (vcnt[a]>2||vcnt[b]>2){isLinear = false;}
        int ra = root(a);
        int rb = root(b);
        if (ra!=rb){
            //rb is new root
            parent[ra]=rb;
            vertices[rb]+=vertices[ra];
            edges[rb]+=edges[ra]+1;
        } else {
            //todo: what happens if we connect in existing cycle
            edges[ra]++;
            numCycles++;
            isLinear = false;
            cycleVertices+=vertices[rb];
        }
    }

    bool connected(int a, int b){
        return root(a)==root(a);
    }

    int getEdges(int x){
        return edges[root(x)];
    }

    int getVertices(int x){
        return vertices[root(x)];
    }
};

vector<vector<int>> adjlist;

vector<UFDS> threeormore;
vector<int> nodesremove;

UFDS mainufds(0);

int numcritical;

vector<pair<int,int>> links;

void Init(int N_) {
    n = N_;
    adjlist.resize(n);
    mainufds = UFDS(n);
    numcritical = n;
}

void Link(int a, int b) {
    if (threeormore.size()>0){
        //just check all four
        numcritical = 0;
        for (int i = 0; i<threeormore.size(); i++){
            if (!(nodesremove[i]==a||nodesremove[i]==b)){
                threeormore[i].connect(a,b);
            }
            if (threeormore[i].isLinear){
                //cout<<i<<' '<<a<<' '<<b<<' '<<'\n';
                numcritical++;
            }
        }
    } else {
        //have we just made three things
        if (adjlist[a].size()!=2&&adjlist[b].size()==2){
            swap(a,b);
        }
        if (adjlist[a].size()==2){
            //vector<int> nodesremove;
            nodesremove.push_back(a);
            for (int i : adjlist[a]){
                nodesremove.push_back(i);
            }
            nodesremove.push_back(b);
            //make new ufds without these nodes
            for (int i = 0; i<4; i++){
                threeormore.push_back(UFDS(n));
                for (auto l : links){
                    if (l.first==nodesremove[i]||l.second==nodesremove[i]){continue;}
                    threeormore[i].connect(l.first, l.second);
                }
            }
            Link(a,b);
            return;
        } else {
            links.push_back({a,b});
            mainufds.connect(a,b);
            adjlist[a].push_back(b);
            adjlist[b].push_back(a);
            if (mainufds.numCycles==0){
                numcritical = n;
            } else if (mainufds.numCycles==1){
                numcritical = mainufds.cycleVertices;
            } else {
                numcritical = 0;
            }
        }
    }
}

int CountCritical() {
    return numcritical;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UFDS>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int i = 0; i<threeormore.size(); i++){
      |                         ~^~~~~~~~~~~~~~~~~~~

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