oj.uz

답안 #766969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
766969 2023-06-26T09:45:05 Z boris_mihov 낙하산 고리들 (IOI12_rings) C++17
20 / 100
 4000 ms 60704 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();
    toNode2.clear();
    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 && i != node)
        {
            return false;
        }
    }
 
    return true;
}

bool isLenThree = false;
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 (cntThree > 10)
        {
            isBad = true;
            return;
        }

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

        if (cntThree > 2)
        {
            ans = 0;
            for (const int &u : three)
            {
                ans += check(u);
            }

            return;
        }
        
        if (cycle && dsu.areConnected(u, v))
        {
            isLenThree = false;
            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))
        {
            for (const int &x : g[u])
            {
                if (x == v)
                {
                    isLenThree = true;
                }
            }
            
            cycle = u;
        }
 
        if (!dsu.areConnected(u, v))
        {
            dsu.connect(u, v);
        }
 
        if (cycle)
        {   
            if (cntThree > 3)
            {
                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 == 3)
            {
                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 == 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;
}

/*
6 14
1 2
-1
1 3
-1
2 3
-1
1 0
-1
3 4
-1
2 5
-1
5 4
-1
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 24084 KB Output is correct
3 Correct 13 ms 24092 KB Output is correct
4 Correct 13 ms 23804 KB Output is correct
5 Correct 13 ms 23952 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 25 ms 24056 KB Output is correct
8 Correct 13 ms 24080 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 53768 KB Output is correct
2 Correct 442 ms 60704 KB Output is correct
3 Execution timed out 4086 ms 56092 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 24084 KB Output is correct
3 Correct 13 ms 24092 KB Output is correct
4 Correct 13 ms 23804 KB Output is correct
5 Correct 13 ms 23952 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 25 ms 24056 KB Output is correct
8 Correct 13 ms 24080 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 90 ms 24296 KB Output is correct
12 Correct 20 ms 24656 KB Output is correct
13 Incorrect 56 ms 24712 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 24084 KB Output is correct
3 Correct 13 ms 24092 KB Output is correct
4 Correct 13 ms 23804 KB Output is correct
5 Correct 13 ms 23952 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 25 ms 24056 KB Output is correct
8 Correct 13 ms 24080 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 90 ms 24296 KB Output is correct
12 Correct 20 ms 24656 KB Output is correct
13 Incorrect 56 ms 24712 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 24084 KB Output is correct
3 Correct 13 ms 24092 KB Output is correct
4 Correct 13 ms 23804 KB Output is correct
5 Correct 13 ms 23952 KB Output is correct
6 Correct 14 ms 24140 KB Output is correct
7 Correct 25 ms 24056 KB Output is correct
8 Correct 13 ms 24080 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 302 ms 53768 KB Output is correct
12 Correct 442 ms 60704 KB Output is correct
13 Execution timed out 4086 ms 56092 KB Time limit exceeded
14 Halted 0 ms 0 KB -