Submission #103810

#	Time	Username	Problem	Language	Result	Execution time	Memory
103810		alexpetrescu	Parachute rings (IOI12_rings)	C++14	100 / 100	1805 ms	121040 KiB

rings

#include <vector>
#include <utility>

#define x first
#define y second

#define MAXN 1000009

std::vector < std::pair < int, int > > muchii;
std::vector < int > g[MAXN];
int n, ans, stare, t[MAXN], s[MAXN];
struct graf {
    int interzis;
    bool bines;
    int t[MAXN], gr[MAXN];
};
std::vector < graf > grafuri;

int sef(int x, int t[]) {
    if (t[x] == x) return x;
    else return t[x] = sef(t[x], t);
}

inline void baga(graf &a, int x, int y) {
    if (a.bines == 0)
        return ;
    if (x == a.interzis || y == a.interzis)
        return ;
    a.gr[x]++;
    a.gr[y]++;
    if (a.gr[x] >= 3 || a.gr[y] >= 3)
        a.bines = 0;
    x = sef(x, a.t);
    y = sef(y, a.t);
    if (x == y)
        a.bines = 0;
    else
        a.t[x] = y;
}

inline void solve(graf &a) {
    a.bines = 1;
    for (int i = 0; i < n; i++)
        a.t[i] = i, a.gr[i] = 0;
    for (auto &x : muchii)
        baga(a, x.x, x.y);
}

void Init(int N_) {
    n = ans = N_;
    for (int i = 0; i < ans; i++)
        t[i] = i, s[i] = 1;
    stare = 1;
}

void Link(int A, int B) {
    if (stare == 4)
        return ;
    if (stare == 3) {
        ans = 0;
        for (auto &x : grafuri) {
            baga(x, A, B);
            ans += x.bines;
        }
        return ;
    }
    muchii.push_back({A, B});
    g[A].push_back(B);
    g[B].push_back(A);
    if ((int)g[A].size() == 3 || (int)g[B].size() == 3) {
        std::vector < int > noduri;
        if ((int)g[A].size() == 3 && (int)g[B].size() == 3)
            noduri.push_back(A), noduri.push_back(B);
        else {
            if ((int)g[A].size() < 3)
                A = B;
            noduri.push_back(A);
            for (auto &x : g[A])
                noduri.push_back(x);
        }
        stare = 3;
        grafuri.resize(noduri.size());
        for (int i = 0; i < (int)grafuri.size(); i++)
            grafuri[i].interzis = noduri[i];
        ans = 0;
        for (auto &x : grafuri) {
            solve(x);
            ans += x.bines;
        }
        return ;
    }
    if (stare == 1) {
        A = sef(A, t);
        B = sef(B, t);
        if (A == B)
            ans = s[A], stare = 2;
        else
            t[A] = B, s[B] += s[A];
        return ;
    }
    /// stare == 2
    A = sef(A, t);
    B = sef(B, t);
    if (A == B)
        ans = 0, stare = 4;
    else
        t[A] = B, s[B] += s[A];
}

int CountCritical() {
    return ans;
}

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