Submission #63419

#	Time	Username	Problem	Language	Result	Execution time	Memory
63419		Vahan	Parachute rings (IOI12_rings)	C++17	55 / 100	4043 ms	86712 KiB

rings

#include<vector>
#include<iostream>
using namespace std;
vector<int> g[2000000];
int n,u[2000000],q,p;
int sz[2000000],pa[2000000];
int CountCritical();
void crset(int a)
{
    sz[a]=1;
    pa[a]=a;
}
int getparent(int a)
{
    if(pa[a]==a)
        return a;
    pa[a]=getparent(pa[a]);
    return pa[a];
}
void setunion(int a,int b)
{
    a=getparent(a);
    b=getparent(b);
    if(a==b)
    {
        q++;
        p+=sz[a];
    }
    if(a>b)
    {
        sz[a]+=sz[b];
        pa[b]=a;
    }
    if(a<b)
    {
        sz[b]+=sz[a];
        pa[a]=b;
    }
}
void dfs(int v)
{
    u[v]=1;
    for(int j=0;j<g[v].size();j++)
    {
        int to=g[v][j];
        if(u[to]==0)
            dfs(to);
    }
}
int stug (int x)
{
    int mq=0;
    for(int i=0;i<n;i++)
    {
        if(i==x)
            continue;
        int qq=0;
        for(int j=0;j<g[i].size();j++)
        {
            int to= g[i][j];
            if(to==x)
                continue;
            qq++;
        }
        if(qq==3)
            return 0;
        if(qq==0)
            mq+=2;
        if(qq==1)
            mq+=1;
    }
    for(int i=0;i<n;i++)
        u[i]=0;
    u[x]=1;
    int xq=0;
    for(int i=0;i<n;i++)
    {
        if(u[i]==0)
        {
            dfs(i);
            xq++;
        }
    }
    if(2*xq==mq)
        return 1;
    else
        return 0;
}
void Init(int N_) {

  n = N_;

}

void Link(int A, int B) {
    g[A].push_back(B);
    g[B].push_back(A);
}

int CountCritical() {
    for(int i=0;i<n;i++)
    {
        if(g[i].size()>=4)
        {
            if(stug(i))
                return 1;
            else
                return 0;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(g[i].size()==3)
        {
            p=0;
            if(stug(i))
                p++;
            for(int j=0;j<g[i].size();j++)
            {
                int to=g[i][j];
                if(stug(to))
                    p++;
            }
            return p;
        }
    }
    p=0;
    q=0;
    for(int i=0;i<n;i++)
        crset(i);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<g[i].size();j++)
        {
            int to=g[i][j];
            if(to>i)
                setunion(i,to);
        }
    }
    if(q==1)
        return p;
    if(q>1)
        return 0;
    if(q==0)
        return n;
}

Compilation message (stderr)

rings.cpp: In function 'void dfs(int)':
rings.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<g[v].size();j++)
                 ~^~~~~~~~~~~~
rings.cpp: In function 'int stug(int)':
rings.cpp:58:22: 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:118:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<g[i].size();j++)
                         ~^~~~~~~~~~~~
rings.cpp:133:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[i].size();j++)
                     ~^~~~~~~~~~~~
rings.cpp:146: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: 0 / 14
• Subtask 5: 0 / 31