oj.uz

Submission #291071

# Submission time Handle Problem Language Result Execution time Memory
291071 2020-09-04T16:03:35 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
100 / 100
 3639 ms 171520 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 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 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 25 ms 25856 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 70 ms 77304 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 26 ms 25984 KB Output is correct
6 Correct 27 ms 26232 KB Output is correct
7 Correct 66 ms 76920 KB Output is correct
8 Correct 26 ms 26112 KB Output is correct
9 Correct 68 ms 77176 KB Output is correct
10 Correct 69 ms 77176 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 65024 KB Output is correct
2 Correct 1953 ms 141576 KB Output is correct
3 Correct 3313 ms 160208 KB Output is correct
4 Correct 1220 ms 114528 KB Output is correct
5 Correct 1210 ms 114644 KB Output is correct
6 Correct 1178 ms 112748 KB Output is correct
7 Correct 3639 ms 171520 KB Output is correct
8 Correct 2130 ms 159708 KB Output is correct
9 Correct 2196 ms 165412 KB Output is correct
10 Correct 919 ms 111740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25856 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 70 ms 77304 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 26 ms 25984 KB Output is correct
6 Correct 27 ms 26232 KB Output is correct
7 Correct 66 ms 76920 KB Output is correct
8 Correct 26 ms 26112 KB Output is correct
9 Correct 68 ms 77176 KB Output is correct
10 Correct 69 ms 77176 KB Output is correct
11 Correct 80 ms 77104 KB Output is correct
12 Correct 81 ms 77432 KB Output is correct
13 Correct 71 ms 77488 KB Output is correct
14 Correct 71 ms 77048 KB Output is correct
15 Correct 69 ms 77432 KB Output is correct
16 Correct 29 ms 26624 KB Output is correct
17 Correct 76 ms 77176 KB Output is correct
18 Correct 84 ms 77560 KB Output is correct
19 Correct 30 ms 26624 KB Output is correct
20 Correct 74 ms 77436 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25856 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 70 ms 77304 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 26 ms 25984 KB Output is correct
6 Correct 27 ms 26232 KB Output is correct
7 Correct 66 ms 76920 KB Output is correct
8 Correct 26 ms 26112 KB Output is correct
9 Correct 68 ms 77176 KB Output is correct
10 Correct 69 ms 77176 KB Output is correct
11 Correct 80 ms 77104 KB Output is correct
12 Correct 81 ms 77432 KB Output is correct
13 Correct 71 ms 77488 KB Output is correct
14 Correct 71 ms 77048 KB Output is correct
15 Correct 69 ms 77432 KB Output is correct
16 Correct 29 ms 26624 KB Output is correct
17 Correct 76 ms 77176 KB Output is correct
18 Correct 84 ms 77560 KB Output is correct
19 Correct 30 ms 26624 KB Output is correct
20 Correct 74 ms 77436 KB Output is correct
21 Correct 50 ms 28844 KB Output is correct
22 Correct 61 ms 30576 KB Output is correct
23 Correct 88 ms 31984 KB Output is correct
24 Correct 132 ms 80120 KB Output is correct
25 Correct 86 ms 80376 KB Output is correct
26 Correct 123 ms 80248 KB Output is correct
27 Correct 101 ms 32276 KB Output is correct
28 Correct 125 ms 79992 KB Output is correct
29 Correct 136 ms 80508 KB Output is correct
30 Correct 113 ms 33260 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25856 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 70 ms 77304 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 26 ms 25984 KB Output is correct
6 Correct 27 ms 26232 KB Output is correct
7 Correct 66 ms 76920 KB Output is correct
8 Correct 26 ms 26112 KB Output is correct
9 Correct 68 ms 77176 KB Output is correct
10 Correct 69 ms 77176 KB Output is correct
11 Correct 516 ms 65024 KB Output is correct
12 Correct 1953 ms 141576 KB Output is correct
13 Correct 3313 ms 160208 KB Output is correct
14 Correct 1220 ms 114528 KB Output is correct
15 Correct 1210 ms 114644 KB Output is correct
16 Correct 1178 ms 112748 KB Output is correct
17 Correct 3639 ms 171520 KB Output is correct
18 Correct 2130 ms 159708 KB Output is correct
19 Correct 2196 ms 165412 KB Output is correct
20 Correct 919 ms 111740 KB Output is correct
21 Correct 80 ms 77104 KB Output is correct
22 Correct 81 ms 77432 KB Output is correct
23 Correct 71 ms 77488 KB Output is correct
24 Correct 71 ms 77048 KB Output is correct
25 Correct 69 ms 77432 KB Output is correct
26 Correct 29 ms 26624 KB Output is correct
27 Correct 76 ms 77176 KB Output is correct
28 Correct 84 ms 77560 KB Output is correct
29 Correct 30 ms 26624 KB Output is correct
30 Correct 74 ms 77436 KB Output is correct
31 Correct 50 ms 28844 KB Output is correct
32 Correct 61 ms 30576 KB Output is correct
33 Correct 88 ms 31984 KB Output is correct
34 Correct 132 ms 80120 KB Output is correct
35 Correct 86 ms 80376 KB Output is correct
36 Correct 123 ms 80248 KB Output is correct
37 Correct 101 ms 32276 KB Output is correct
38 Correct 125 ms 79992 KB Output is correct
39 Correct 136 ms 80508 KB Output is correct
40 Correct 113 ms 33260 KB Output is correct
41 Correct 344 ms 57708 KB Output is correct
42 Correct 998 ms 133248 KB Output is correct
43 Correct 379 ms 110328 KB Output is correct
44 Correct 975 ms 110568 KB Output is correct
45 Correct 1161 ms 121452 KB Output is correct
46 Correct 934 ms 99736 KB Output is correct
47 Correct 1126 ms 101204 KB Output is correct
48 Correct 647 ms 114168 KB Output is correct
49 Correct 840 ms 103484 KB Output is correct
50 Correct 872 ms 102616 KB Output is correct
51 Correct 435 ms 105464 KB Output is correct
52 Correct 818 ms 103800 KB Output is correct
53 Correct 677 ms 113656 KB Output is correct
54 Correct 1669 ms 144348 KB Output is correct
55 Correct 1497 ms 117096 KB Output is correct