oj.uz

Submission #291048

# Submission time Handle Problem Language Result Execution time Memory
291048 2020-09-04T15:56:23 Z stoyan_malinin Parachute rings (IOI12_rings) C++14
20 / 100
 4000 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);
}

void initFirst()
{
    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(excludedNode.empty()==true)
        {
            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 60 ms 72700 KB Output is correct
2 Correct 203 ms 218360 KB Output is correct
3 Correct 210 ms 218488 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 61 ms 72952 KB Output is correct
6 Correct 71 ms 73108 KB Output is correct
7 Correct 215 ms 217848 KB Output is correct
8 Correct 61 ms 72952 KB Output is correct
9 Correct 226 ms 218528 KB Output is correct
10 Correct 218 ms 218488 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 72700 KB Output is correct
2 Correct 203 ms 218360 KB Output is correct
3 Correct 210 ms 218488 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 61 ms 72952 KB Output is correct
6 Correct 71 ms 73108 KB Output is correct
7 Correct 215 ms 217848 KB Output is correct
8 Correct 61 ms 72952 KB Output is correct
9 Correct 226 ms 218528 KB Output is correct
10 Correct 218 ms 218488 KB Output is correct
11 Correct 419 ms 254928 KB Output is correct
12 Correct 258 ms 219384 KB Output is correct
13 Correct 213 ms 219232 KB Output is correct
14 Correct 201 ms 217852 KB Output is correct
15 Correct 201 ms 217976 KB Output is correct
16 Correct 65 ms 73324 KB Output is correct
17 Execution timed out 4099 ms 219064 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 72700 KB Output is correct
2 Correct 203 ms 218360 KB Output is correct
3 Correct 210 ms 218488 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 61 ms 72952 KB Output is correct
6 Correct 71 ms 73108 KB Output is correct
7 Correct 215 ms 217848 KB Output is correct
8 Correct 61 ms 72952 KB Output is correct
9 Correct 226 ms 218528 KB Output is correct
10 Correct 218 ms 218488 KB Output is correct
11 Correct 419 ms 254928 KB Output is correct
12 Correct 258 ms 219384 KB Output is correct
13 Correct 213 ms 219232 KB Output is correct
14 Correct 201 ms 217852 KB Output is correct
15 Correct 201 ms 217976 KB Output is correct
16 Correct 65 ms 73324 KB Output is correct
17 Execution timed out 4099 ms 219064 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 72700 KB Output is correct
2 Correct 203 ms 218360 KB Output is correct
3 Correct 210 ms 218488 KB Output is correct
4 Correct 61 ms 72824 KB Output is correct
5 Correct 61 ms 72952 KB Output is correct
6 Correct 71 ms 73108 KB Output is correct
7 Correct 215 ms 217848 KB Output is correct
8 Correct 61 ms 72952 KB Output is correct
9 Correct 226 ms 218528 KB Output is correct
10 Correct 218 ms 218488 KB Output is correct
11 Correct 573 ms 99804 KB Output is correct
12 Runtime error 664 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -