oj.uz

Submission #291075

# Submission time Handle Problem Language Result Execution time Memory
291075 2020-09-04T16:05:53 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
55 / 100
 3727 ms 159692 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);
        auto it = excludedNode.find(node);

        for(pair <int, int> e: G.allEdges)
        {
            if(e.first!=node && e.second!=node)
            {
                it->second.addEdge(e.first, e.second);
            }
        }
    }
}

void Link(int A, int B)
{
    if(G.maxDeg==3)
    {
        if(initFirstCalled==false)
        {
            initFirst();
        }
    }
    else if(G.maxDeg>=4)
    {
        if(initSecondCalled==false)
        {
            initSecond();
        }
    }

    G.addEdge(A, B, true);
    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 26 ms 25848 KB Output is correct
2 Correct 76 ms 77048 KB Output is correct
3 Correct 72 ms 77176 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 27 ms 26104 KB Output is correct
6 Correct 28 ms 26240 KB Output is correct
7 Correct 69 ms 76984 KB Output is correct
8 Correct 27 ms 26104 KB Output is correct
9 Correct 73 ms 77116 KB Output is correct
10 Correct 74 ms 77176 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 65288 KB Output is correct
2 Correct 2004 ms 137736 KB Output is correct
3 Correct 3399 ms 148032 KB Output is correct
4 Correct 1220 ms 101588 KB Output is correct
5 Correct 1254 ms 101548 KB Output is correct
6 Correct 1210 ms 100092 KB Output is correct
7 Correct 3727 ms 159692 KB Output is correct
8 Correct 2169 ms 147332 KB Output is correct
9 Correct 2177 ms 152160 KB Output is correct
10 Correct 930 ms 99284 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25848 KB Output is correct
2 Correct 76 ms 77048 KB Output is correct
3 Correct 72 ms 77176 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 27 ms 26104 KB Output is correct
6 Correct 28 ms 26240 KB Output is correct
7 Correct 69 ms 76984 KB Output is correct
8 Correct 27 ms 26104 KB Output is correct
9 Correct 73 ms 77116 KB Output is correct
10 Correct 74 ms 77176 KB Output is correct
11 Correct 83 ms 77048 KB Output is correct
12 Correct 91 ms 77560 KB Output is correct
13 Correct 83 ms 77612 KB Output is correct
14 Correct 75 ms 77176 KB Output is correct
15 Correct 79 ms 77560 KB Output is correct
16 Correct 31 ms 26744 KB Output is correct
17 Correct 77 ms 77176 KB Output is correct
18 Correct 94 ms 77560 KB Output is correct
19 Correct 31 ms 26744 KB Output is correct
20 Correct 76 ms 77560 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25848 KB Output is correct
2 Correct 76 ms 77048 KB Output is correct
3 Correct 72 ms 77176 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 27 ms 26104 KB Output is correct
6 Correct 28 ms 26240 KB Output is correct
7 Correct 69 ms 76984 KB Output is correct
8 Correct 27 ms 26104 KB Output is correct
9 Correct 73 ms 77116 KB Output is correct
10 Correct 74 ms 77176 KB Output is correct
11 Correct 83 ms 77048 KB Output is correct
12 Correct 91 ms 77560 KB Output is correct
13 Correct 83 ms 77612 KB Output is correct
14 Correct 75 ms 77176 KB Output is correct
15 Correct 79 ms 77560 KB Output is correct
16 Correct 31 ms 26744 KB Output is correct
17 Correct 77 ms 77176 KB Output is correct
18 Correct 94 ms 77560 KB Output is correct
19 Correct 31 ms 26744 KB Output is correct
20 Correct 76 ms 77560 KB Output is correct
21 Correct 49 ms 28916 KB Output is correct
22 Correct 62 ms 30704 KB Output is correct
23 Correct 76 ms 32112 KB Output is correct
24 Correct 136 ms 80084 KB Output is correct
25 Correct 88 ms 80376 KB Output is correct
26 Correct 149 ms 80232 KB Output is correct
27 Correct 104 ms 32364 KB Output is correct
28 Correct 134 ms 79992 KB Output is correct
29 Incorrect 122 ms 80504 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25848 KB Output is correct
2 Correct 76 ms 77048 KB Output is correct
3 Correct 72 ms 77176 KB Output is correct
4 Correct 25 ms 25856 KB Output is correct
5 Correct 27 ms 26104 KB Output is correct
6 Correct 28 ms 26240 KB Output is correct
7 Correct 69 ms 76984 KB Output is correct
8 Correct 27 ms 26104 KB Output is correct
9 Correct 73 ms 77116 KB Output is correct
10 Correct 74 ms 77176 KB Output is correct
11 Correct 534 ms 65288 KB Output is correct
12 Correct 2004 ms 137736 KB Output is correct
13 Correct 3399 ms 148032 KB Output is correct
14 Correct 1220 ms 101588 KB Output is correct
15 Correct 1254 ms 101548 KB Output is correct
16 Correct 1210 ms 100092 KB Output is correct
17 Correct 3727 ms 159692 KB Output is correct
18 Correct 2169 ms 147332 KB Output is correct
19 Correct 2177 ms 152160 KB Output is correct
20 Correct 930 ms 99284 KB Output is correct
21 Correct 83 ms 77048 KB Output is correct
22 Correct 91 ms 77560 KB Output is correct
23 Correct 83 ms 77612 KB Output is correct
24 Correct 75 ms 77176 KB Output is correct
25 Correct 79 ms 77560 KB Output is correct
26 Correct 31 ms 26744 KB Output is correct
27 Correct 77 ms 77176 KB Output is correct
28 Correct 94 ms 77560 KB Output is correct
29 Correct 31 ms 26744 KB Output is correct
30 Correct 76 ms 77560 KB Output is correct
31 Correct 49 ms 28916 KB Output is correct
32 Correct 62 ms 30704 KB Output is correct
33 Correct 76 ms 32112 KB Output is correct
34 Correct 136 ms 80084 KB Output is correct
35 Correct 88 ms 80376 KB Output is correct
36 Correct 149 ms 80232 KB Output is correct
37 Correct 104 ms 32364 KB Output is correct
38 Correct 134 ms 79992 KB Output is correct
39 Incorrect 122 ms 80504 KB Output isn't correct
40 Halted 0 ms 0 KB -