Submission #63587

#	Time	Username	Problem	Language	Result	Execution time	Memory
63587		Vahan	Parachute rings (IOI12_rings)	C++17	100 / 100	3220 ms	173036 KiB

rings

#include<vector>
#include<iostream>
using namespace std;
vector<int> g[2000000];
int n,u[2000000],q[8],p[8];
int sz[2000000][8],pa[2000000][8],kq[2000000][8],ynt1[5],ynt2=-1,minchev2=1,y=0,kk[7],ee;
int CountCritical();
void crset(int a,int c)
{
    sz[a][c]=1;
    pa[a][c]=a;
}
int getparent(int a,int c)
{
    if(pa[a][c]==a)
        return a;
    pa[a][c]=getparent(pa[a][c],c);
    return pa[a][c];
}
void setunion(int a,int b,int c)
{
    a=getparent(a,c);
    b=getparent(b,c);
    if(a==b)
    {
        q[c]++;
        p[c]+=sz[a][c];
    }
    if(a>b)
    {
        sz[a][c]+=sz[b][c];
        pa[b][c]=a;
    }
    if(a<b)
    {
        sz[b][c]+=sz[a][c];
        pa[a][c]=b;
    }
}
void Init(int N_) {

    n = N_;
    for(int i=0;i<n;i++)
            crset(i,4);
}

void Link(int A, int B) {
    g[A].push_back(B);
    g[B].push_back(A);
    kq[A][7]++;kq[B][7]++;
    if(kq[A][7]<kq[B][7])
        swap(A,B);
    if(ynt2!=-1)
    {
        if(ynt2!=A && ynt2!=B)
        {
            kq[A][5]++;
            kq[B][5]++;
            if(kq[A][5]>2 || kq[B][5]>2)
                kk[5]=1;
            setunion(A,B,5);
        }
    }
    if(kq[A][7]>=4 && ynt2==-1)
    {
        ynt2=A;
        for(int i=0;i<n;i++)
            crset(i,5);
        for(int i=0;i<n;i++)
        {
            if(A==i)
                continue;
            for(int j=0;j<g[i].size();j++)
            {
                int to=g[i][j];
                if(to==A)
                    continue;
                if(to>i)
                {
                    setunion(to,i,5);
                    kq[to][5]++;
                    kq[i][5]++;
                    if(kq[to][5]>2 || kq[i][5]>2)
                        kk[5]=1;
                }
            }
        }
    }
    if(ynt2==-1 && minchev2==0)
    {
        for(int e=0;e<4;e++)
        {
            if(ynt1[e]==A || ynt1[e]==B)
                continue;
            kq[A][e]++;
            kq[B][e]++;
            if(kq[A][e]>2 || kq[B][e]>2)
                kk[e]=1;
            setunion(A,B,e);
        }
    }
    if(kq[A][7]==3 && ynt2==-1 && minchev2==1)
    {
        minchev2=0;
        ynt1[0]=A;
        for(int i=0;i<g[A].size();i++)
            ynt1[i+1]=g[A][i];
        for(int e=0;e<4;e++)
        {
            for(int i=0;i<n;i++)
            {
                if(i==ynt1[e])
                    continue;
                crset(i,e);
            }
            for(int i=0;i<n;i++)
            {
                if(i==ynt1[e])
                    continue;
                for(int j=0;j<g[i].size();j++)
                {
                    int to=g[i][j];
                    if(to==ynt1[e])
                        continue;
                    if(to>i)
                    {
                        setunion(i,to,e);
                        kq[to][e]++;
                        kq[i][e]++;
                        if(kq[to][e]>2 || kq[i][e]>2)
                            kk[e]=1;
                    }
                }
            }
        }
    }
    if(minchev2==1)
        setunion(A,B,4);
}

int CountCritical() {
    if(minchev2==1)
    {
        if(q[4]==1)
            return p[4];
        if(q[4]>1)
            return 0;
        if(q[4]==0)
            return n;
    }
    else if(ynt2!=-1)
    {
        if(q[5]==0 && kk[5]==0)
            return 1;
        else
            return 0;
    }
    else
    {
        int u=0;
        for(int e=0;e<4;e++)
        {
            if(q[e]==0 && kk[e]==0)
                u++;
        }
        return u;
    }
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<g[i].size();j++)
                         ~^~~~~~~~~~~~
rings.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[A].size();i++)
                     ~^~~~~~~~~~~~
rings.cpp:120:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<g[i].size();j++)
                             ~^~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:168:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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