제출 #766893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766893		boris_mihov	낙하산 고리들 (IOI12_rings)	C++17	0 / 100	4069 ms	60504 KiB

rings

#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 CountCritical2() 
{
    if (isBad) return 0;
    if (theNode != -1) return 1;
    return ans;
}

int CountCritical() 
{
    int res = CountCritical2();
    int res2 = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        res2 += check(i);
    }

    assert(res == res2);
    return res;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31