Submission #1091425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091425		ThegeekKnight16	Parachute rings (IOI12_rings)	C++17	100 / 100	1488 ms	256176 KiB

rings

#include <bits/stdc++.h>
using namespace std;
class Dsu
{
protected:
    vector<int> pai, sub, grau;
    bool isCicle;
    int maxGrau;

public:
    Dsu (int N = 0) : pai(N), sub(N, 1), grau(N, 0), isCicle(0), maxGrau(0) {iota(pai.begin(), pai.end(), 0);}

    int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
    void une(int x, int y)
    {
        grau[x]++; grau[y]++;
        maxGrau = max({maxGrau, grau[x], grau[y]});
        x = find(x), y = find(y);
        if (x == y) {isCicle = 1; return;}
        if (sub[x] < sub[y]) swap(x, y);
        pai[y] = x; sub[x] += sub[y];
    }
    bool isGood() {return !isCicle && (maxGrau < 3);}
};

vector<set<int>> grafo;
vector<int> pai, sub, grau;
vector<bool> isCicle;
int critNum = 0, cicleNum = 0, degreeNum = 0, degreeV;
vector<int> tam3;
vector<pair<int, int>> edges;
map<int, Dsu> without;
int N;

void Init(int _N)
{
    N = _N;
    pai.resize(N); iota(pai.begin(), pai.end(), 0);
    sub.resize(N); fill(sub.begin(), sub.end(), 1);
    grau.resize(N); fill(grau.begin(), grau.end(), 0);
    isCicle.resize(N); fill(isCicle.begin(), isCicle.end(), false);
    grafo.clear(); grafo.resize(N); edges.clear(); tam3.clear();
    without.clear();
    critNum = N, cicleNum = 0, degreeNum = 0;
}

int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void LinkCicle(int A, int B)
{
    if (critNum == 0) return;
    int P = find(A);
    cicleNum -= isCicle[P];
    isCicle[P] = 1;
    cicleNum += isCicle[P];
    if (cicleNum > 1) critNum = 0;
    else critNum = sub[P];
}
void Link3(int A, int B)
{
    if (tam3.size() > 3) {critNum = 0; return;}
    set<int> poss(tam3.begin(), tam3.end());
    for (auto x : tam3)
        for (auto viz : grafo[x])
            poss.insert(viz);

    critNum = 0;
    for (auto x : poss)
    {
        if (!without.count(x))
        {
            without[x] = Dsu(N);
            auto &atual = without[x];
            for (auto [i, j] : edges)
                if (i != x && j != x)
                    atual.une(i, j);
        }
        else if (A != x && B != x) without[x].une(A, B);
        critNum += without[x].isGood();
    }
}
void LinkDegree(int A, int B)
{
    if (A == degreeV || B == degreeV) return;
    without.begin()->second.une(A, B);
    critNum = without.begin()->second.isGood();
}
void buildDegree()
{
    without.clear();
    without[degreeV] = Dsu(N);
    for (auto [A, B] : edges) LinkDegree(A, B);
}

void Link(int A, int B)
{
    edges.emplace_back(A, B);
    if (critNum == 0) return;
    if (degreeNum) {LinkDegree(A, B); return;}
    grafo[A].insert(B), grafo[B].insert(A);

    degreeNum -= (grau[A] >= 4), degreeNum -= (grau[B] >= 4);
    grau[A]++; grau[B]++;
    degreeNum += (grau[A] >= 4), degreeNum += (grau[B] >= 4);
    if (degreeNum > 1) {critNum = 0; return;}
    else if (degreeNum) {degreeV = (grau[A] >= 4 ? A : B); buildDegree(); return;}

    if (grau[A] == 3) tam3.push_back(A);
    if (grau[B] == 3) tam3.push_back(B);
    if (!tam3.empty()) {Link3(A, B); return;}

    int PA = find(A), PB = find(B);
    if (PA == PB) {LinkCicle(A, B); return;}
    if (sub[PA] < sub[PB]) swap(PA, PB);
    pai[PB] = PA; sub[PA] += sub[PB]; isCicle[PA] = (isCicle[PA] || isCicle[PB]);
}

int CountCritical() {return critNum;}

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