Submission #291038

#	Time	Username	Problem	Language	Result	Execution time	Memory
291038		stoyan_malinin	Parachute rings (IOI12_rings)	C++14	52 / 100	313 ms	40368 KiB

rings

//#include "grader.cpp"

#include <set>
#include <map>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 1e5 + 5;

struct Graph
{
    struct DSU
    {
        int n;
        int deg[MAXN];
        int parent[MAXN], treeSize[MAXN];

        bool isBad[MAXN];
        int badComponentSz;
        int components, badComponents;

        DSU(){}
        DSU(int n)
        {
            this->n = n;
            this->components = n;
            this->badComponents = 0;

            for(int i = 0;i<n;i++)
            {
                this->deg[i] = 0;
                this->parent[i] = i;
                this->treeSize[i] = 1;
                this->isBad[i] = false;
            }
        }

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

            parent[x] = Find(parent[x]);
            return parent[x];
        }

        void Union(int u, int v)
        {
            int uOrig = u, vOrig = v;
            u = Find(u);
            v = Find(v);

            badComponents -= isBad[u];
            badComponents -= isBad[v];

            isBad[u] |= isBad[v];
            if(deg[uOrig]>1 || deg[vOrig]>1) isBad[u] = true;

            parent[v] = u;
            treeSize[u] += treeSize[v];

            badComponents += isBad[u];
            if(isBad[u]==true) badComponentSz = treeSize[u];

        }

        void addEdge(int u, int v)
        {
            if(Find(u)!=Find(v))
            {
                Union(u, v);
            }
            else
            {
                if(isBad[Find(u)]==false)
                {
                    isBad[Find(u)] = true;

                    badComponents++;
                    badComponentSz = treeSize[Find(u)];
                }
            }

            deg[u]++;
            deg[v]++;
        }
    };

    int n;
    DSU T;

    int maxDeg = 0;
    vector <int> adj[MAXN];
    vector <pair <int, int>> allEdges;

    int superDegCnt = 0;

    Graph(){}
    Graph(int n)
    {
        this->n = n;
        T = DSU(n);
    }

    void addEdge(int u, int v)
    {
        T.addEdge(u, v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        allEdges.push_back({u, v});

        maxDeg = max(maxDeg, int(adj[u].size()));
        maxDeg = max(maxDeg, int(adj[v].size()));

        if(adj[u].size()==4) superDegCnt++;
        if(adj[v].size()==4) superDegCnt++;
    }
};

Graph G;
map <int, Graph> excludedNode;

void Init(int N)
{
    G = Graph(N);
}

void initFirst()
{
    int node = -1;
    for(int x = 0;x<G.n;x++)
    {
        if(G.adj[x].size()==3)
        {
            node = x;
            break;
        }
    }

    excludedNode[node] = Graph(G.n);
    for(int x: G.adj[node]) excludedNode[x] = Graph(G.n);

    for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
    {
        int x = it->first;
        Graph &g = it->second;

        for(pair <int, int> e: G.allEdges)
        {
            if(e.first!=x && e.second!=x)
            {
                g.addEdge(e.first, e.second);
            }
        }
    }
}

bool initSecondCalled = false;
void initSecond()
{
    initSecondCalled = true;

    int node = -1;
    for(int x = 0;x<G.n;x++)
    {
        if(G.adj[x].size()>=4)
        {
            node = x;
            break;
        }
    }

    if(excludedNode.count(node)==false)
    {
        excludedNode[node] = Graph(G.n);
        for(pair <int, int> e: G.allEdges)
        {
            if(e.first!=node && e.second!=node)
            {
                excludedNode[node].addEdge(e.first, e.second);
            }
        }
    }
}

void Link(int A, int B)
{
    G.addEdge(A, B);

    if(G.maxDeg==3)
    {
        if(excludedNode.empty()==true)
        {
            initFirst();
        }
        else
        {
            for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
            {
                int x = it->first;
                Graph &g = it->second;

                if(A!=x && B!=x)
                {
                    g.addEdge(A, B);
                }
            }
        }
    }
    else if(G.maxDeg>=4)
    {
        if(initSecondCalled==false)
        {
            for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
            {
                int x = it->first;
                Graph &g = it->second;

                if(A!=x && B!=x)
                {
                    g.addEdge(A, B);
                }
            }

            initSecond();
        }
        else
        {
            for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
            {
                int x = it->first;
                Graph &g = it->second;

                if(A!=x && B!=x)
                {
                    g.addEdge(A, B);
                }
            }
        }
    }
}

int CountCritical()
{
    if(G.maxDeg<=2)
    {
        if(G.T.badComponents>1) return 0;
        if(G.T.badComponents==1) return G.T.badComponentSz;

        return G.n;
    }

    assert(excludedNode.size()<=5);

    int ans = 0;
    for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
    {
        if(it->second.T.badComponents==0 && it->second.maxDeg<=2)
        {
            //cout << " -> " << it->first << " " << it->second.maxDeg << '\n';
            ans++;
        }
    }

    return ans;
}

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