oj.uz

Submission #766973

# Submission time Handle Problem Language Result Execution time Memory
766973 2023-06-26T09:46:22 Z boris_mihov Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 59712 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)
        {
            d2[v]--;
            continue;
        }
 
        if (v == node)
        {
            d2[u]--;
            continue;
        }
 
        if (dsu2.areConnected(u, v))
        {
            return false;
        }
 
        dsu2.connect(u, v);
    }
 
    for (int i = 1 ; i <= n ; ++i)
    {
        if (d2[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 10 ms 23820 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 10 ms 23980 KB Output is correct
4 Correct 10 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 15 ms 24120 KB Output is correct
7 Correct 13 ms 24008 KB Output is correct
8 Correct 10 ms 24020 KB Output is correct
9 Correct 11 ms 24148 KB Output is correct
10 Correct 11 ms 24176 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 52216 KB Output is correct
2 Correct 434 ms 59712 KB Output is correct
3 Execution timed out 4072 ms 55856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23820 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 10 ms 23980 KB Output is correct
4 Correct 10 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 15 ms 24120 KB Output is correct
7 Correct 13 ms 24008 KB Output is correct
8 Correct 10 ms 24020 KB Output is correct
9 Correct 11 ms 24148 KB Output is correct
10 Correct 11 ms 24176 KB Output is correct
11 Correct 85 ms 24248 KB Output is correct
12 Correct 15 ms 24556 KB Output is correct
13 Incorrect 50 ms 24532 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23820 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 10 ms 23980 KB Output is correct
4 Correct 10 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 15 ms 24120 KB Output is correct
7 Correct 13 ms 24008 KB Output is correct
8 Correct 10 ms 24020 KB Output is correct
9 Correct 11 ms 24148 KB Output is correct
10 Correct 11 ms 24176 KB Output is correct
11 Correct 85 ms 24248 KB Output is correct
12 Correct 15 ms 24556 KB Output is correct
13 Incorrect 50 ms 24532 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23820 KB Output is correct
2 Correct 11 ms 24020 KB Output is correct
3 Correct 10 ms 23980 KB Output is correct
4 Correct 10 ms 23888 KB Output is correct
5 Correct 14 ms 23980 KB Output is correct
6 Correct 15 ms 24120 KB Output is correct
7 Correct 13 ms 24008 KB Output is correct
8 Correct 10 ms 24020 KB Output is correct
9 Correct 11 ms 24148 KB Output is correct
10 Correct 11 ms 24176 KB Output is correct
11 Correct 318 ms 52216 KB Output is correct
12 Correct 434 ms 59712 KB Output is correct
13 Execution timed out 4072 ms 55856 KB Time limit exceeded
14 Halted 0 ms 0 KB -