Submission #1035653

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035653		12345678	Parachute rings (IOI12_rings)	C++17	100 / 100	602 ms	103564 KiB

rings

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

int n, dsu[nx], deg[nx], c, sz[nx], cy, res;
vector<int> d[nx];
vector<pair<int, int>> edg;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

struct universe
{
    int rt, pa[nx], ans, deg[nx];
    int find(int x)
    {
        if (pa[x]==x) return x;
        return pa[x]=find(pa[x]);
    }
    void merge(int u, int v)
    {
        if (u==rt||v==rt||ans==0) return;
        if (++deg[u]==3) ans=0;
        if (++deg[v]==3) ans=0;
        if (find(u)==find(v)) ans=0;
        else pa[find(u)]=find(v);
    }
    void init()
    {
        ans=1;
        for (int i=0; i<n; i++) pa[i]=i;
        for (auto x:edg) merge(x.first, x.second);
    }
} uni[4];

void Init(int N_) {
    n=N_;
    for (int i=0; i<n; i++) dsu[i]=i, sz[i]=1;
}

void Link(int A, int B) {
    if (c) for (int i=0; i<4; i++) uni[i].merge(A, B);
    else
    {
        edg.push_back({A, B});
        d[A].push_back(B);
        d[B].push_back(A);
        if (deg[A]+1==3||deg[B]+1==3) c=1;
        if (++deg[A]==3)
        {
            uni[0].rt=A;
            for (int i=0; i<3; i++) uni[1+i].rt=d[A][i];
            for (int i=0; i<4; i++) uni[i].init();
            return;
        }
        if (++deg[B]==3)
        {
            uni[0].rt=B;
            for (int i=0; i<3; i++) uni[1+i].rt=d[B][i];
            for (int i=0; i<4; i++) uni[i].init();
            return;
        }
        if (find(A)!=find(B)) sz[find(A)]+=sz[find(B)], dsu[find(B)]=find(A);
        else res=sz[find(A)], cy++;
    }
}

int CountCritical() {
    if (cy>1) return 0;
    if (c) return uni[0].ans+uni[1].ans+uni[2].ans+uni[3].ans;
    if (cy==1) return res;
    return n;
}

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