oj.uz

Submission #291878

# Submission time Handle Problem Language Result Execution time Memory
291878 2020-09-05T22:53:50 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
100 / 100
 3678 ms 171496 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 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25848 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 73 ms 77180 KB Output is correct
4 Correct 27 ms 25848 KB Output is correct
5 Correct 27 ms 26112 KB Output is correct
6 Correct 33 ms 26240 KB Output is correct
7 Correct 68 ms 77048 KB Output is correct
8 Correct 27 ms 26240 KB Output is correct
9 Correct 71 ms 77176 KB Output is correct
10 Correct 73 ms 77176 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 72104 KB Output is correct
2 Correct 1943 ms 147672 KB Output is correct
3 Correct 3342 ms 159776 KB Output is correct
4 Correct 1213 ms 113372 KB Output is correct
5 Correct 1217 ms 113340 KB Output is correct
6 Correct 1185 ms 111832 KB Output is correct
7 Correct 3678 ms 171496 KB Output is correct
8 Correct 2116 ms 159312 KB Output is correct
9 Correct 2164 ms 163944 KB Output is correct
10 Correct 910 ms 110932 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25848 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 73 ms 77180 KB Output is correct
4 Correct 27 ms 25848 KB Output is correct
5 Correct 27 ms 26112 KB Output is correct
6 Correct 33 ms 26240 KB Output is correct
7 Correct 68 ms 77048 KB Output is correct
8 Correct 27 ms 26240 KB Output is correct
9 Correct 71 ms 77176 KB Output is correct
10 Correct 73 ms 77176 KB Output is correct
11 Correct 84 ms 77176 KB Output is correct
12 Correct 86 ms 77560 KB Output is correct
13 Correct 78 ms 77560 KB Output is correct
14 Correct 75 ms 77176 KB Output is correct
15 Correct 73 ms 77560 KB Output is correct
16 Correct 30 ms 26752 KB Output is correct
17 Correct 74 ms 77176 KB Output is correct
18 Correct 91 ms 77732 KB Output is correct
19 Correct 31 ms 26776 KB Output is correct
20 Correct 75 ms 77564 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25848 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 73 ms 77180 KB Output is correct
4 Correct 27 ms 25848 KB Output is correct
5 Correct 27 ms 26112 KB Output is correct
6 Correct 33 ms 26240 KB Output is correct
7 Correct 68 ms 77048 KB Output is correct
8 Correct 27 ms 26240 KB Output is correct
9 Correct 71 ms 77176 KB Output is correct
10 Correct 73 ms 77176 KB Output is correct
11 Correct 84 ms 77176 KB Output is correct
12 Correct 86 ms 77560 KB Output is correct
13 Correct 78 ms 77560 KB Output is correct
14 Correct 75 ms 77176 KB Output is correct
15 Correct 73 ms 77560 KB Output is correct
16 Correct 30 ms 26752 KB Output is correct
17 Correct 74 ms 77176 KB Output is correct
18 Correct 91 ms 77732 KB Output is correct
19 Correct 31 ms 26776 KB Output is correct
20 Correct 75 ms 77564 KB Output is correct
21 Correct 48 ms 29300 KB Output is correct
22 Correct 62 ms 31216 KB Output is correct
23 Correct 74 ms 32752 KB Output is correct
24 Correct 127 ms 80248 KB Output is correct
25 Correct 87 ms 80504 KB Output is correct
26 Correct 132 ms 80376 KB Output is correct
27 Correct 84 ms 33260 KB Output is correct
28 Correct 124 ms 80120 KB Output is correct
29 Correct 122 ms 80632 KB Output is correct
30 Correct 102 ms 34412 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25848 KB Output is correct
2 Correct 74 ms 77048 KB Output is correct
3 Correct 73 ms 77180 KB Output is correct
4 Correct 27 ms 25848 KB Output is correct
5 Correct 27 ms 26112 KB Output is correct
6 Correct 33 ms 26240 KB Output is correct
7 Correct 68 ms 77048 KB Output is correct
8 Correct 27 ms 26240 KB Output is correct
9 Correct 71 ms 77176 KB Output is correct
10 Correct 73 ms 77176 KB Output is correct
11 Correct 510 ms 72104 KB Output is correct
12 Correct 1943 ms 147672 KB Output is correct
13 Correct 3342 ms 159776 KB Output is correct
14 Correct 1213 ms 113372 KB Output is correct
15 Correct 1217 ms 113340 KB Output is correct
16 Correct 1185 ms 111832 KB Output is correct
17 Correct 3678 ms 171496 KB Output is correct
18 Correct 2116 ms 159312 KB Output is correct
19 Correct 2164 ms 163944 KB Output is correct
20 Correct 910 ms 110932 KB Output is correct
21 Correct 84 ms 77176 KB Output is correct
22 Correct 86 ms 77560 KB Output is correct
23 Correct 78 ms 77560 KB Output is correct
24 Correct 75 ms 77176 KB Output is correct
25 Correct 73 ms 77560 KB Output is correct
26 Correct 30 ms 26752 KB Output is correct
27 Correct 74 ms 77176 KB Output is correct
28 Correct 91 ms 77732 KB Output is correct
29 Correct 31 ms 26776 KB Output is correct
30 Correct 75 ms 77564 KB Output is correct
31 Correct 48 ms 29300 KB Output is correct
32 Correct 62 ms 31216 KB Output is correct
33 Correct 74 ms 32752 KB Output is correct
34 Correct 127 ms 80248 KB Output is correct
35 Correct 87 ms 80504 KB Output is correct
36 Correct 132 ms 80376 KB Output is correct
37 Correct 84 ms 33260 KB Output is correct
38 Correct 124 ms 80120 KB Output is correct
39 Correct 122 ms 80632 KB Output is correct
40 Correct 102 ms 34412 KB Output is correct
41 Correct 273 ms 57624 KB Output is correct
42 Correct 927 ms 133344 KB Output is correct
43 Correct 401 ms 110328 KB Output is correct
44 Correct 938 ms 110456 KB Output is correct
45 Correct 1103 ms 121452 KB Output is correct
46 Correct 851 ms 99932 KB Output is correct
47 Correct 1039 ms 101216 KB Output is correct
48 Correct 657 ms 114168 KB Output is correct
49 Correct 804 ms 103660 KB Output is correct
50 Correct 842 ms 102740 KB Output is correct
51 Correct 423 ms 105464 KB Output is correct
52 Correct 799 ms 103800 KB Output is correct
53 Correct 673 ms 113616 KB Output is correct
54 Correct 1598 ms 144516 KB Output is correct
55 Correct 1538 ms 117220 KB Output is correct