oj.uz

답안 #766885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766885 2023-06-26T08:35:48 Z boris_mihov 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 907 ms 79524 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 == 2);
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 13 ms 24004 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 13 ms 24060 KB Output is correct
7 Correct 11 ms 23920 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 13 ms 24068 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 284 ms 52300 KB Output is correct
2 Correct 430 ms 59644 KB Output is correct
3 Correct 157 ms 40268 KB Output is correct
4 Correct 896 ms 78868 KB Output is correct
5 Correct 907 ms 79092 KB Output is correct
6 Correct 862 ms 77948 KB Output is correct
7 Correct 154 ms 40300 KB Output is correct
8 Correct 824 ms 75656 KB Output is correct
9 Correct 885 ms 79524 KB Output is correct
10 Correct 595 ms 77120 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 13 ms 24004 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 13 ms 24060 KB Output is correct
7 Correct 11 ms 23920 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 13 ms 24068 KB Output is correct
11 Runtime error 31 ms 48844 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 13 ms 24004 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 13 ms 24060 KB Output is correct
7 Correct 11 ms 23920 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 13 ms 24068 KB Output is correct
11 Runtime error 31 ms 48844 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 13 ms 24004 KB Output is correct
4 Correct 13 ms 23888 KB Output is correct
5 Correct 12 ms 24020 KB Output is correct
6 Correct 13 ms 24060 KB Output is correct
7 Correct 11 ms 23920 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 13 ms 24148 KB Output is correct
10 Correct 13 ms 24068 KB Output is correct
11 Correct 284 ms 52300 KB Output is correct
12 Correct 430 ms 59644 KB Output is correct
13 Correct 157 ms 40268 KB Output is correct
14 Correct 896 ms 78868 KB Output is correct
15 Correct 907 ms 79092 KB Output is correct
16 Correct 862 ms 77948 KB Output is correct
17 Correct 154 ms 40300 KB Output is correct
18 Correct 824 ms 75656 KB Output is correct
19 Correct 885 ms 79524 KB Output is correct
20 Correct 595 ms 77120 KB Output is correct
21 Runtime error 31 ms 48844 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -