Submission #432761

#	Time	Username	Problem	Language	Result	Execution time	Memory
432761		JeanBombeur	Parachute rings (IOI12_rings)	C++17	100 / 100	1097 ms	52932 KiB

rings

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

//    <|°_°|>

const int MAX_NOEUDS = (1000 * 1000);

int Dsu[4][MAX_NOEUDS];
int Deg[4][MAX_NOEUDS];

pair <int, int> Aretes[MAX_NOEUDS];
int nbAretes = 0;

bool IsCritical[4];
int NoeudOut[4];

int nbNoeuds;
bool isSplit = false;
int tailleCycle = 0;

int Find(int id, int a) {
    if (Dsu[id][a] < 0)
        return a;
    return Dsu[id][a] = Find(id, Dsu[id][a]);
}

bool Union(int id, int nb) {
    int rA = Find(id, Aretes[nb].first), rB = Find(id, Aretes[nb].second);
    if (rA == rB)
        return false;
    if (Dsu[id][rA] > Dsu[id][rB])
        swap(rA, rB);
    Dsu[id][rA] += Dsu[id][rB];
    Dsu[id][rB] = rA;
    return true;
}

void ConstructWithout(int id, int noeud) {
    IsCritical[id] = true;
    NoeudOut[id] = noeud;
    for (int i = 0; i < nbAretes; i ++)
    {
        if (noeud != Aretes[i].first && noeud != Aretes[i].second)
        {
            IsCritical[id] &= Union(id, i);
            IsCritical[id] &= ++ Deg[id][Aretes[i].first] <= 2;
            IsCritical[id] &= ++ Deg[id][Aretes[i].second] <= 2;
        }
    }
    return;
}

void Reconstruct(int a) {
    for (int i = 0; i < nbNoeuds; i ++)
    {
        Deg[0][i] = 0;
        Dsu[0][i] = -1;
    }
    isSplit = true;
    vector <int> nv;
    nv.push_back(a);
    for (int i = 0; i < nbAretes; i ++)
    {
        if (Aretes[i].first == a || Aretes[i].second == a)
            nv.push_back(Aretes[i].second ^ Aretes[i].first ^ a);
    }
    for (int i = 0; i < 4; i ++)
    {
        ConstructWithout(i, nv[i]);
    }
    return;
}

void Init(int n) {
    for (int i = 0; i < 4; i ++)
    {
        for (int j = 0; j < n; j ++)
        {
            Dsu[i][j] = -1;
        }
    }
    nbNoeuds = n;
    return;
}

void Link(int a, int b) {
    Aretes[nbAretes ++] = {a, b};
    if (!isSplit)
    {
        if (Deg[0][a] < Deg[0][b])
            swap(a, b);
        if (!Union(0, nbAretes - 1))
        {
            if (tailleCycle == 0)
                tailleCycle = - Dsu[0][Find(0, a)];
            else
                tailleCycle = -1;
        }
        Deg[0][b] ++;
        if (++ Deg[0][a] == 3)
            Reconstruct(a);
    }
    else
    {
        for (int i = 0; i < 4; i ++)
        {
            if (NoeudOut[i] != a && NoeudOut[i] != b)
            {
                IsCritical[i] &= ++ Deg[i][a] <= 2;
                IsCritical[i] &= ++ Deg[i][b] <= 2;
                IsCritical[i] &= Union(i, nbAretes - 1);
            }
        }
    }
    return;
}

int CountCritical() {
    if (!isSplit)
    {
        if (tailleCycle == 0)
            return nbNoeuds;
        if (tailleCycle > 0)
            return tailleCycle;
        return 0;
    }
    int nb = 0;
    for (int i = 0; i < 4; i ++)
    {
        nb += IsCritical[i];
    }
    return nb;
}

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