oj.uz

Submission #291038

# Submission time Handle Problem Language Result Execution time Memory
291038 2020-09-04T15:49:48 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
52 / 100
 313 ms 40368 KB 
//#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7552 KB Output is correct
2 Correct 27 ms 22912 KB Output is correct
3 Correct 29 ms 23288 KB Output is correct
4 Correct 7 ms 7680 KB Output is correct
5 Correct 8 ms 7808 KB Output is correct
6 Correct 10 ms 7936 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 30 ms 23288 KB Output is correct
10 Correct 28 ms 23296 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 17792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7552 KB Output is correct
2 Correct 27 ms 22912 KB Output is correct
3 Correct 29 ms 23288 KB Output is correct
4 Correct 7 ms 7680 KB Output is correct
5 Correct 8 ms 7808 KB Output is correct
6 Correct 10 ms 7936 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 30 ms 23288 KB Output is correct
10 Correct 28 ms 23296 KB Output is correct
11 Correct 33 ms 27000 KB Output is correct
12 Correct 42 ms 28152 KB Output is correct
13 Correct 37 ms 24312 KB Output is correct
14 Correct 32 ms 23296 KB Output is correct
15 Correct 32 ms 23296 KB Output is correct
16 Correct 11 ms 8192 KB Output is correct
17 Correct 37 ms 24184 KB Output is correct
18 Correct 54 ms 28920 KB Output is correct
19 Correct 12 ms 8192 KB Output is correct
20 Correct 37 ms 24448 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7552 KB Output is correct
2 Correct 27 ms 22912 KB Output is correct
3 Correct 29 ms 23288 KB Output is correct
4 Correct 7 ms 7680 KB Output is correct
5 Correct 8 ms 7808 KB Output is correct
6 Correct 10 ms 7936 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 30 ms 23288 KB Output is correct
10 Correct 28 ms 23296 KB Output is correct
11 Correct 33 ms 27000 KB Output is correct
12 Correct 42 ms 28152 KB Output is correct
13 Correct 37 ms 24312 KB Output is correct
14 Correct 32 ms 23296 KB Output is correct
15 Correct 32 ms 23296 KB Output is correct
16 Correct 11 ms 8192 KB Output is correct
17 Correct 37 ms 24184 KB Output is correct
18 Correct 54 ms 28920 KB Output is correct
19 Correct 12 ms 8192 KB Output is correct
20 Correct 37 ms 24448 KB Output is correct
21 Correct 29 ms 9460 KB Output is correct
22 Correct 41 ms 10480 KB Output is correct
23 Correct 58 ms 11408 KB Output is correct
24 Correct 241 ms 32596 KB Output is correct
25 Correct 51 ms 24568 KB Output is correct
26 Correct 234 ms 36052 KB Output is correct
27 Correct 61 ms 12140 KB Output is correct
28 Correct 313 ms 40368 KB Output is correct
29 Correct 188 ms 37860 KB Output is correct
30 Correct 79 ms 13804 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7552 KB Output is correct
2 Correct 27 ms 22912 KB Output is correct
3 Correct 29 ms 23288 KB Output is correct
4 Correct 7 ms 7680 KB Output is correct
5 Correct 8 ms 7808 KB Output is correct
6 Correct 10 ms 7936 KB Output is correct
7 Correct 22 ms 22272 KB Output is correct
8 Correct 8 ms 7808 KB Output is correct
9 Correct 30 ms 23288 KB Output is correct
10 Correct 28 ms 23296 KB Output is correct
11 Runtime error 19 ms 17792 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -