oj.uz

Submission #291061

# Submission time Handle Problem Language Result Execution time Memory
291061 2020-09-04T16:00:00 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
52 / 100
 2730 ms 262148 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 = 1e6 + 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, 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)
{
    G = Graph(N);
}

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 Link(int A, int B)
{
    G.addEdge(A, B, true);

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

            initSecond();
        }
        else
        {
            for(auto it = excludedNode.begin();it!=excludedNode.end();it++)
            {
                int x = it->first;
                if(A!=x && B!=x)
                {
                    it->second.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;
    }

    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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 72696 KB Output is correct
2 Correct 212 ms 217848 KB Output is correct
3 Correct 201 ms 217976 KB Output is correct
4 Correct 60 ms 72824 KB Output is correct
5 Correct 60 ms 72952 KB Output is correct
6 Correct 61 ms 73080 KB Output is correct
7 Correct 195 ms 217720 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 198 ms 217976 KB Output is correct
10 Correct 197 ms 217976 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 99816 KB Output is correct
2 Correct 2054 ms 262144 KB Output is correct
3 Runtime error 2730 ms 262148 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 72696 KB Output is correct
2 Correct 212 ms 217848 KB Output is correct
3 Correct 201 ms 217976 KB Output is correct
4 Correct 60 ms 72824 KB Output is correct
5 Correct 60 ms 72952 KB Output is correct
6 Correct 61 ms 73080 KB Output is correct
7 Correct 195 ms 217720 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 198 ms 217976 KB Output is correct
10 Correct 197 ms 217976 KB Output is correct
11 Correct 238 ms 217848 KB Output is correct
12 Correct 238 ms 218104 KB Output is correct
13 Correct 201 ms 218104 KB Output is correct
14 Correct 205 ms 217740 KB Output is correct
15 Correct 197 ms 217848 KB Output is correct
16 Correct 64 ms 73336 KB Output is correct
17 Correct 203 ms 217844 KB Output is correct
18 Correct 247 ms 218052 KB Output is correct
19 Correct 65 ms 73336 KB Output is correct
20 Correct 206 ms 218116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 72696 KB Output is correct
2 Correct 212 ms 217848 KB Output is correct
3 Correct 201 ms 217976 KB Output is correct
4 Correct 60 ms 72824 KB Output is correct
5 Correct 60 ms 72952 KB Output is correct
6 Correct 61 ms 73080 KB Output is correct
7 Correct 195 ms 217720 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 198 ms 217976 KB Output is correct
10 Correct 197 ms 217976 KB Output is correct
11 Correct 238 ms 217848 KB Output is correct
12 Correct 238 ms 218104 KB Output is correct
13 Correct 201 ms 218104 KB Output is correct
14 Correct 205 ms 217740 KB Output is correct
15 Correct 197 ms 217848 KB Output is correct
16 Correct 64 ms 73336 KB Output is correct
17 Correct 203 ms 217844 KB Output is correct
18 Correct 247 ms 218052 KB Output is correct
19 Correct 65 ms 73336 KB Output is correct
20 Correct 206 ms 218116 KB Output is correct
21 Correct 81 ms 74612 KB Output is correct
22 Correct 93 ms 75760 KB Output is correct
23 Correct 109 ms 76528 KB Output is correct
24 Correct 255 ms 218876 KB Output is correct
25 Correct 214 ms 218872 KB Output is correct
26 Correct 257 ms 218980 KB Output is correct
27 Correct 144 ms 77292 KB Output is correct
28 Correct 260 ms 218948 KB Output is correct
29 Correct 278 ms 219260 KB Output is correct
30 Correct 135 ms 77928 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 72696 KB Output is correct
2 Correct 212 ms 217848 KB Output is correct
3 Correct 201 ms 217976 KB Output is correct
4 Correct 60 ms 72824 KB Output is correct
5 Correct 60 ms 72952 KB Output is correct
6 Correct 61 ms 73080 KB Output is correct
7 Correct 195 ms 217720 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 198 ms 217976 KB Output is correct
10 Correct 197 ms 217976 KB Output is correct
11 Correct 536 ms 99816 KB Output is correct
12 Correct 2054 ms 262144 KB Output is correct
13 Runtime error 2730 ms 262148 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -