Submission #290960

#	Time	Username	Problem	Language	Result	Execution time	Memory
290960		stoyan_malinin	Parachute rings (IOI12_rings)	C++14	0 / 100	276 ms	262148 KiB

rings

//#include "grader.cpp"

#include <set>
#include <map>
#include <vector>
#include <cstring>
#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;

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

Graph G;
map <int, Graph> excludedNode;

void Init(int N)
{
    G = Graph(N);
    for(int x = 0;x<N;x++) excludedNode[x] = 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);
            }
        }
    }
}

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

    /*
    if(G.maxDeg>=3 && 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);
            }
        }
    }*/

    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;
    }
    if(G.maxDeg>3)
    {
        return 0;
    }

    int ans = 0;
    for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
    {
        if(it->second.T.badComponents==0) ans++;
    }

    return ans;
}

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