Submission #155978

#	Time	Username	Problem	Language	Result	Execution time	Memory
155978		Alexa2001	Parachute rings (IOI12_rings)	C++17	100 / 100	917 ms	62064 KiB

rings

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 5;

int n;
bool big = 0, cycle = 0;
vector<int> cand;
vector<pair<int,int>> edges;

int grad[5][Nmax];
bool ok[Nmax];
int ans;


struct FO
{
    int t[Nmax];

    void init()
    {
        int i;
        for(i=0; i<n; ++i) t[i] = i;
    }

    int boss(int x)
    {
        if(t[x] == x) return x;
        return t[x] = boss(t[x]);
    }

    bool unite(int x, int y)
    {
        x = boss(x); y = boss(y);
        if(x == y) return 0;
        t[x] = y;
        return 1;
    }
} forest[5];

void Init(int N)
{
    n = N;
    ans = n;
    forest[4].init();

    int i, j;
    for(i=0; i<n; ++i)
        for(j=0; j<5; ++j)
            grad[j][i] = 0, ok[i] = 0;
}

void transf(int node)
{
    big = 1;

    int i;
    for(auto it : edges)
        if(it.first == node)
            cand.push_back(it.second);
        else if(it.second == node)
            cand.push_back(it.first);

    cand.push_back(node);

    int id = -1;
    for(auto el : cand)
    {
        ++id;
        ok[el] = 1;
        forest[id].init();

        for(auto it : edges)
            if(it.first != el && it.second != el)
            {
                ++grad[id][it.first], ++grad[id][it.second];
                ok[el] &= forest[id].unite(it.first, it.second);
            }
    }

    ans = 0;
    id = -1;
    for(auto it : cand)
    {
        ++id;
        for(i=0; i<n; ++i)
            ok[it] &= (grad[id][i] <= 2);

        if(ok[it]) ++ans;
    }
}

void Link(int A, int B)
{
    edges.push_back({A, B});

    if(!big)
    {
        ++grad[4][A];
        ++grad[4][B];

        if(grad[4][A] == 3) transf(A);
            else if(grad[4][B] == 3) transf(B);
                else
        if(!forest[4].unite(A, B))
        {
            if(!cycle)
            {
                cycle = 1;
                int i;
                ans = 0;
                for(i=0; i<n; ++i)
                    if(forest[4].boss(i) == forest[4].boss(A)) ok[i] = 1, ++ans;
            }
            else ans = 0;
        }
        return;
    }

    int id = -1;
    for(auto el : cand)
    {
        ++id;
        if(!ok[el]) continue;

        if(el != A && el != B)
        {
            ++grad[id][A];
            ++grad[id][B];

            ans --;

            ok[el] &= forest[id].unite(A, B);
            ok[el] &= (grad[id][A] <= 2 && grad[id][B] <= 2);

            ans += ok[el];
        }
    }
}

int CountCritical()
{
    return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31