oj.uz

Submission #766970

# Submission time Handle Problem Language Result Execution time Memory
766970 2023-06-26T09:45:34 Z boris_mihov Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 59632 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 > 4)
        {
            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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24056 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 12 ms 23820 KB Output is correct
5 Correct 13 ms 23972 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 17 ms 24100 KB Output is correct
8 Correct 14 ms 24084 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

# Verdict Execution time Memory Grader output
1 Correct 296 ms 52280 KB Output is correct
2 Correct 439 ms 59632 KB Output is correct
3 Execution timed out 4070 ms 55940 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24056 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 12 ms 23820 KB Output is correct
5 Correct 13 ms 23972 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 17 ms 24100 KB Output is correct
8 Correct 14 ms 24084 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 86 ms 24252 KB Output is correct
12 Correct 16 ms 24568 KB Output is correct
13 Incorrect 55 ms 24616 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24056 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 12 ms 23820 KB Output is correct
5 Correct 13 ms 23972 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 17 ms 24100 KB Output is correct
8 Correct 14 ms 24084 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 86 ms 24252 KB Output is correct
12 Correct 16 ms 24568 KB Output is correct
13 Incorrect 55 ms 24616 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 14 ms 24056 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 12 ms 23820 KB Output is correct
5 Correct 13 ms 23972 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 17 ms 24100 KB Output is correct
8 Correct 14 ms 24084 KB Output is correct
9 Correct 14 ms 24148 KB Output is correct
10 Correct 14 ms 24148 KB Output is correct
11 Correct 296 ms 52280 KB Output is correct
12 Correct 439 ms 59632 KB Output is correct
13 Execution timed out 4070 ms 55940 KB Time limit exceeded
14 Halted 0 ms 0 KB -