oj.uz

Submission #291056

# Submission time Handle Problem Language Result Execution time Memory
291056 2020-09-04T15:57:51 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
52 / 100
 636 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);
        adj[u].push_back(v);
        adj[v].push_back(u);
        if(mode==true) 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);
}

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 59 ms 72696 KB Output is correct
2 Correct 210 ms 218336 KB Output is correct
3 Correct 214 ms 218508 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 62 ms 72952 KB Output is correct
6 Correct 62 ms 73080 KB Output is correct
7 Correct 203 ms 217772 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 209 ms 218484 KB Output is correct
10 Correct 203 ms 218488 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 99768 KB Output is correct
2 Runtime error 636 ms 262148 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 72696 KB Output is correct
2 Correct 210 ms 218336 KB Output is correct
3 Correct 214 ms 218508 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 62 ms 72952 KB Output is correct
6 Correct 62 ms 73080 KB Output is correct
7 Correct 203 ms 217772 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 209 ms 218484 KB Output is correct
10 Correct 203 ms 218488 KB Output is correct
11 Correct 251 ms 218360 KB Output is correct
12 Correct 249 ms 219256 KB Output is correct
13 Correct 219 ms 219384 KB Output is correct
14 Correct 209 ms 217868 KB Output is correct
15 Correct 208 ms 217848 KB Output is correct
16 Correct 66 ms 73340 KB Output is correct
17 Correct 210 ms 217976 KB Output is correct
18 Correct 257 ms 218104 KB Output is correct
19 Correct 66 ms 73336 KB Output is correct
20 Correct 218 ms 219256 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 72696 KB Output is correct
2 Correct 210 ms 218336 KB Output is correct
3 Correct 214 ms 218508 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 62 ms 72952 KB Output is correct
6 Correct 62 ms 73080 KB Output is correct
7 Correct 203 ms 217772 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 209 ms 218484 KB Output is correct
10 Correct 203 ms 218488 KB Output is correct
11 Correct 251 ms 218360 KB Output is correct
12 Correct 249 ms 219256 KB Output is correct
13 Correct 219 ms 219384 KB Output is correct
14 Correct 209 ms 217868 KB Output is correct
15 Correct 208 ms 217848 KB Output is correct
16 Correct 66 ms 73340 KB Output is correct
17 Correct 210 ms 217976 KB Output is correct
18 Correct 257 ms 218104 KB Output is correct
19 Correct 66 ms 73336 KB Output is correct
20 Correct 218 ms 219256 KB Output is correct
21 Correct 83 ms 74612 KB Output is correct
22 Correct 99 ms 75696 KB Output is correct
23 Correct 111 ms 76592 KB Output is correct
24 Correct 290 ms 218872 KB Output is correct
25 Correct 219 ms 218872 KB Output is correct
26 Correct 285 ms 219128 KB Output is correct
27 Correct 115 ms 77292 KB Output is correct
28 Correct 267 ms 219128 KB Output is correct
29 Correct 284 ms 219896 KB Output is correct
30 Correct 137 ms 78060 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 72696 KB Output is correct
2 Correct 210 ms 218336 KB Output is correct
3 Correct 214 ms 218508 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 62 ms 72952 KB Output is correct
6 Correct 62 ms 73080 KB Output is correct
7 Correct 203 ms 217772 KB Output is correct
8 Correct 60 ms 72952 KB Output is correct
9 Correct 209 ms 218484 KB Output is correct
10 Correct 203 ms 218488 KB Output is correct
11 Correct 581 ms 99768 KB Output is correct
12 Runtime error 636 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -