Submission #767092

#	Time	Username	Problem	Language	Result	Execution time	Memory
767092		boris_mihov	Parachute rings (IOI12_rings)	C++17	100 / 100	1481 ms	82212 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)
        {
            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 (cycle && dsu.areConnected(u, v))
        {
            if (dsu.find(u) != dsu.find(cycle))
            {
                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 (cntThree != 0 && cycle != 0)
        {
            std::set <int> good123;
            if (cntThree <= 2)
            {
                for (const int &u : three)
                {
                    good123.insert(u);
                    for (const int &i : g[u])
                        good123.insert(i);
                }
            } else
            {
                for (const int &u : three)
                {
                    good123.insert(u);
                }
            }
 
            ans = 0;
            for (const int &u : good123)
            {
                ans += check(u);
            }
 
            return;
        }
 
        if (cycle)
        {   
            ans = dsu.sz[dsu.find(cycle)];
            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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31