Submission #291878

#	Time	Username	Problem	Language	Result	Execution time	Memory
291878		stoyan_malinin	Parachute rings (IOI12_rings)	C++14	100 / 100	3678 ms	171496 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 = 1e6 + 5;

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]++;
    }
};

struct Graph
{
    int n;
    DSU T;

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

    int superDegCnt = 0;

    Graph(){}
    Graph(int n, bool mode = false)
    {
        this->n = n;
        if(mode==true) adj.resize(n);

        T = DSU(n);
    }

    void addEdge(int u, int v, bool mode = false)
    {
        T.addEdge(u, v);
        if(mode==true)
        {
            adj[u].push_back(v);
            adj[v].push_back(u);
            allEdges.push_back({u, v});
        }

        maxDeg = max(maxDeg, int(T.deg[u]));
        maxDeg = max(maxDeg, int(T.deg[v]));

        if(T.deg[u]==4) superDegCnt++;
        if(T.deg[v]==4) superDegCnt++;
    }
};

Graph G;
map <int, Graph> excludedNode;

void Init(int N)
{
    //cout << double(sizeof(Graph))/(1024*1024) << '\n';
    G = Graph(N, true);
}

bool initFirstCalled = false;
void initFirst()
{
    initFirstCalled = true;

    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;
        for(pair <int, int> e: G.allEdges)
        {
            if(e.first!=x && e.second!=x)
            {
                it->second.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 addEdge(int A, int B)
{
    for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
    {
        int x = it->first;
        if(A!=x && B!=x)
        {
            it->second.addEdge(A, B);
        }
    }
}

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

    if(G.maxDeg==3)
    {
        if(initFirstCalled==false)
        {
            initFirst();
        }
        else
        {
            addEdge(A, B);
        }
    }
    else if(G.maxDeg>=4)
    {
        addEdge(A, B);
        if(initSecondCalled==false)
        {
            initSecond();
        }
    }
}

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;
    }

    int ans = 0;
    vector <int> toRemove;
    for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
    {
        if(it->second.T.badComponents==0 && it->second.maxDeg<=2)
        {
            ans++;
        }
        else
        {
            toRemove.push_back(it->first);
        }
    }

    for(int rem: toRemove) excludedNode.erase(rem);
    return ans;
}

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