Submission #254657

#	Time	Username	Problem	Language	Result	Execution time	Memory
254657		MKopchev	Parachute rings (IOI12_rings)	C++14	0 / 100	1405 ms	104912 KiB

rings

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e6+42;

int n;

int deg[10][nmax];

int ret;

vector< int > adj[nmax];

int parent[10][nmax];
int SZ[nmax];

void Init(int N)
{
    n=N;

    ret=n;

    for(int i=0;i<n;i++)
    {
        parent[0][i]=i;
        SZ[i]=1;
    }
}

set<int> big;

bool forced_small_group=0;

int root(int id,int node)
{
    if(parent[id][node]==node)return parent[id][node];
    parent[id][node]=root(id,parent[id][node]);
    return parent[id][node];
}

bool cycle;

vector< pair<int,int> > edges;

set<int> nums;

int ordered[10],pointer=0;
bool valid[10];

void small_group(int A,int B)
{
    //cout<<"small group "<<A<<" "<<B<<endl;

    for(int i=1;i<=pointer;i++)
        if(valid[i]&&A!=ordered[i]&&B!=ordered[i])
        {
            deg[i][A]++;
            deg[i][B]++;

            if(root(i,A)==root(i,B)||deg[i][A]>=3||deg[i][B]>=3)
            {
                valid[i]=0;
                ret--;
                continue;
            }

            parent[i][root(i,A)]=root(i,B);
        }

    //for(int i=1;i<=pointer;i++)cout<<ordered[i]<<" "<<valid[i]<<endl;
}
void create_small()
{
    for(auto k:big)
    {
        nums.insert(k);
        for(auto p:adj[k])
            nums.insert(p);
    }

    ret=0;
    for(auto k:nums)
    {
        pointer++;
        ordered[pointer]=k;
        valid[pointer]=1;
        ret++;

        for(int j=0;j<n;j++)
            parent[pointer][j]=j;

        //cout<<"k= "<<k<<endl;
    }

    for(auto k:edges)
        small_group(k.first,k.second);
}

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

    adj[A].push_back(B);
    adj[B].push_back(A);

    if(ret==0)return;

    if(forced_small_group)
    {
        small_group(A,B);
        return;
    }

    deg[0][A]++;
    deg[0][B]++;

    if(deg[0][A]>=3)big.insert(A);
    if(deg[0][B]>=3)big.insert(B);

    if(big.size()>=1)
    {
        forced_small_group=1;
        create_small();
        return;
    }

    if(root(0,A)!=root(0,B))
    {
        parent[0][root(0,A)]=root(0,B);
        SZ[root(0,B)]+=SZ[root(0,A)];
        return;
    }

    //a cycle with no degrees >=3
    if(cycle)
    {
        ret=0;
        return;
    }

    cycle=1;
    ret=SZ[root(0,A)];
}
int CountCritical()
{
    return ret;
}
/*
int main()
{
    Init(7);
    cout<<CountCritical()<<endl;//7
    Link(1, 2);
    cout<<CountCritical()<<endl;//7
    Link(0, 5);
    cout<<CountCritical()<<endl;//7
    Link(2, 0);
    cout<<CountCritical()<<endl;//7
    Link(3, 2);
    cout<<CountCritical()<<endl;//4
    Link(3, 5);
    cout<<CountCritical()<<endl;//3
    Link(4, 3);
    cout<<CountCritical()<<endl;//2
    return 0;
}
*/

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