oj.uz

Submission #766862

# Submission time Handle Problem Language Result Execution time Memory
766862 2023-06-26T08:17:07 Z boris_mihov Parachute rings (IOI12_rings) C++17
0 / 100
 325 ms 54180 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF  = 1e9;

int n;
int d[MAXN];
struct DSU
{
    int par[MAXN];
    int dep[MAXN];
    int sz[MAXN];

    void build()
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            par[i] = i;
            dep[i] = 1;
            sz[i] = 1;
        }
    }

    int find(int u)
    {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    void connect(int u, int v)
    {
        u = find(u);
        v = find(v);

        if (u == v)
        {
            assert(false);
            return;
        }

        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        if (dep[u] == dep[v])
        {
            dep[v]++;
        }

        par[u] = v;
        sz[v] += sz[u];
    }

    bool areConnected(int u, int v)
    {
        return find(u) == find(v);
    }
};

DSU dsu;
int ans;
void Init(int N_) 
{
    n = N_;
    ans = n;
    dsu.build();
}

int cycle;
bool isBad;
int cntThree;
int theNode = -1;
std::set <int> toNode;
std::vector <int> three;
std::vector <std::pair <int,int>> added;
std::vector <int> g[MAXN];

void reConnect(int node)
{
    dsu.build();
    theNode = node;
    std::fill(d + 1, d + 1 + n, 0);
    for (const auto &[u, v] : added)
    {
        d[u]++;
        d[v]++;
        if (u == node)
        {
            toNode.insert(v);
            continue;
        }

        if (v == node)
        {
            toNode.insert(u);
            continue;
        }

        if (dsu.areConnected(u, v))
        {
            isBad = true;
            return;
        }

        dsu.connect(u, v);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (d[i] - toNode.count(i) > 2)
        {
            isBad = true;
            return;
        }
    }
}

void Link(int u, int v)
{
    u++;
    v++;
    if (isBad)
    {
        return;
    }

    added.push_back({u, v});
    if (theNode != -1)
    {
        if (v == theNode)
        {
            std::swap(u, v);
        }

        if (u == theNode)
        {
            d[v]++;
            toNode.insert(v);
            if (d[v] > 3)
            {
                isBad = true;
                return;
            }
        } else
        {
            d[v]++;
            d[u]++;
            if (d[v] - toNode.count(v) > 2)
            {
                isBad = true;
                return;
            }

            if (d[u] - toNode.count(u) > 2)
            {
                isBad = true;
                return;
            }

            if (dsu.areConnected(u, v))
            {
                isBad = true;
                return;
            }

            dsu.connect(u, v);
        }
    } else
    {
        d[u]++;
        d[v]++;
        if (d[u] == 4 && d[v] == 4)
        {
            isBad = true;
            return;
        }

        if (d[u] == 4)
        {
            reConnect(u);
            return;
        }

        if (d[v] == 4)
        {
            reConnect(v);
            return;
        }

        cntThree += (d[u] == 3);
        cntThree += (d[v] == 3);

        if (cycle && dsu.areConnected(u, v))
        {
            if (dsu.find(u) != dsu.find(cycle))
            {
                isBad = true;
                return;
            }
        }

        if (!cycle && dsu.areConnected(u, v))
        {
            cycle = dsu.find(u);
        }

        if (!dsu.areConnected(u, v))
        {
            dsu.connect(u, v);
        }

        g[u].push_back(v);
        g[v].push_back(u);

        if (d[u] == 3)
        {
            three.push_back(u);
        }

        if (d[v] == 3)
        {
            three.push_back(v);
        }

        if (cycle)
        {
            if (cntThree > 2)
            {
                isBad = true;
                return;
            }

            for (const int &u : three)
            {
                if (dsu.find(u) != dsu.find(cycle))
                {
                    isBad = true;
                    return;
                }
            }

            if (cntThree == 0)
            {
                ans = dsu.sz[dsu.find(cycle)];
                return;
            }

            if (cntThree == 1)
            {
                ans = 3;
                return;
            }

            ans = 2;
            return;
        }

        if (cntThree > 4)
        {
            isBad = true;
            return;
        }

        if (cntThree == 0)
        {
            ans = n;
            return;
        }

        if (cntThree == 1)
        {
            ans = 4;
            return;
        }

        ans = 0;
        for (const int &i : three)
        {
            int curr = 0;
            for (const int &u : g[i])
            {
                curr += (d[u] == 3);
            }

            if (curr == cntThree - 1)
            {
                ans++;
            }
        }

        if (cntThree == 2)
        {
            bool good = false;
            for (const int &u : g[three[0]])
            {
                for (const int &v : g[three[1]])
                {
                    if (u == v)
                    {
                        ans++;
                        good = true;
                        break;
                    }
                }

                if (good)
                {
                    break;
                }
            }
        }
    }
}

int CountCritical() 
{
    if (isBad) return 0;
    if (theNode != -1) return 1;
    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 13 ms 24008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 52284 KB Output is correct
2 Incorrect 325 ms 54180 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 13 ms 24008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 13 ms 24008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Incorrect 13 ms 24008 KB Output isn't correct
3 Halted 0 ms 0 KB -