oj.uz

Submission #766890

# Submission time Handle Problem Language Result Execution time Memory
766890 2023-06-26T08:37:38 Z boris_mihov Parachute rings (IOI12_rings) C++17
37 / 100
 923 ms 78488 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];
int d2[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;
DSU dsu2;
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::set <int> toNode2;
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 && i != node)
        {
            isBad = true;
            return;
        }
    }
}

bool check(int node)
{
    dsu2.build();
    std::fill(d2 + 1, d2 + 1 + n, 0);
    for (const auto &[u, v] : added)
    {
        d2[u]++;
        d2[v]++;
        if (u == node)
        {
            toNode2.insert(v);
            continue;
        }

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

        if (dsu2.areConnected(u, v))
        {
            return false;
        }

        dsu2.connect(u, v);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (d2[i] - toNode2.count(i) > 2)
        {
            return false;
        }
    }

    return true;
}

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);

        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 && dsu.areConnected(u, v))
        {
            if (dsu.find(u) != dsu.find(cycle))
            {
                isBad = true;
                return;
            }

            assert(cntThree > 1);
            if (!check(three[0]))
            {
                isBad = true;
                return;
            }
        }

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

        if (!dsu.areConnected(u, v))
        {
            dsu.connect(u, 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 == 2)
            {
                bool good = false;
                for (const int &i : g[three[0]])
                {   
                    if (i == three[1])
                    {
                        good = true;
                    }
                }

                if (!good)
                {
                    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)
        {
            for (const int &u : g[three[0]])
            {
                for (const int &v : g[three[1]])
                {
                    if (u == v)
                    {
                        ans++;
                    }
                }
            }
        }
    }
}

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24088 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 11 ms 23860 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 16 ms 24136 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 16 ms 24148 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 52236 KB Output is correct
2 Correct 475 ms 59652 KB Output is correct
3 Correct 174 ms 40300 KB Output is correct
4 Correct 923 ms 78472 KB Output is correct
5 Correct 882 ms 78488 KB Output is correct
6 Correct 865 ms 77172 KB Output is correct
7 Correct 161 ms 40320 KB Output is correct
8 Correct 848 ms 75048 KB Output is correct
9 Correct 909 ms 78468 KB Output is correct
10 Correct 589 ms 76360 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24088 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 11 ms 23860 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 16 ms 24136 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 16 ms 24148 KB Output is correct
11 Incorrect 15 ms 24148 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24088 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 11 ms 23860 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 16 ms 24136 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 16 ms 24148 KB Output is correct
11 Incorrect 15 ms 24148 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 13 ms 24088 KB Output is correct
3 Correct 15 ms 24092 KB Output is correct
4 Correct 11 ms 23860 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 16 ms 24136 KB Output is correct
7 Correct 11 ms 23892 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 16 ms 24148 KB Output is correct
11 Correct 301 ms 52236 KB Output is correct
12 Correct 475 ms 59652 KB Output is correct
13 Correct 174 ms 40300 KB Output is correct
14 Correct 923 ms 78472 KB Output is correct
15 Correct 882 ms 78488 KB Output is correct
16 Correct 865 ms 77172 KB Output is correct
17 Correct 161 ms 40320 KB Output is correct
18 Correct 848 ms 75048 KB Output is correct
19 Correct 909 ms 78468 KB Output is correct
20 Correct 589 ms 76360 KB Output is correct
21 Incorrect 15 ms 24148 KB Output isn't correct
22 Halted 0 ms 0 KB -