Submission #790239

#	Time	Username	Problem	Language	Result	Execution time	Memory
790239		Amylopectin	Parachute rings (IOI12_rings)	C++14	37 / 100	931 ms	196960 KiB

rings

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 4e6 + 10;
// const int mxn = 110;
vector<int> pat[mxn] = {};
int n,ggr[mxn] = {},see[mxn] = {},deg[mxn] = {},inn[mxn] = {},rus,ruc
,thi[mxn] = {},cyc[mxn] = {},ocy,ret,u[mxn] = {},of;
int figr(int l)
{
  int cn = l,f;
  while(ggr[l] != l)
  {
    l = ggr[l];
  }
  while(ggr[cn] != cn)
  {
    f = ggr[cn];
    ggr[cn] = l;
    cn = f;
  }
  return l;
}
int mer(int l,int r)
{
  int f,cl = figr(l),cr = figr(r);
  if(cl > cr)
  {
    f = cl;
    cl = cr;
    cr = f;
  }
  ggr[cr] = cl;
  // nmem[cl] += nmem[cr];
  return cl;
}
int re(int cn,int be)
{
    int i,j,fn,fou = 0,cva;
    if(cyc[cn] == 1)
    {
        ocy = 1;
        ret = cn;
        return 1;
    }
    u[cn] = 1;
    for(i=0; i<pat[cn].size(); i++)
    {
        fn = pat[cn][i];
        if(fn == be)
        {
            continue;
        }
        if(u[fn] == 1)
        {
            fou = 1;
            break;
        }
        cva = re(fn,cn);
        if(cva == 1)
        {
            fou = 1;
            break;
        }
    }
    u[cn] = 0;
    if(fou == 1)
    {
        cyc[cn] = 1;
        if(thi[cn] == 1 || of == 1)
        {
            inn[ruc] = cn;
            ruc ++;
        }
    }
    return fou;
}
void Init(int nn)
{
    int i,j;
    n = nn;
    for(i=0; i<n; i++)
    {
        ggr[i] = i;
        see[i] = i;
        cyc[i] = 0;
    }
    rus = n;
}
void Link(int cl, int cr)
{
    int gl = figr(cl),gr = figr(cr),f,cru,cruc,i,j;
    pat[cl].push_back(cr);
    pat[cr].push_back(cl);
    deg[cl] ++;
    deg[cr] ++;
    mer(gl,gr);
    if(rus == 0)
    {
        return ;
    }
    ruc = 0;
    if(deg[cl] < deg[cr])
    {
        f = cl;
        cl = cr;
        cr = f;
        f = gl;
        gl = gr;
        gr = f;
    }
    if(deg[cl] > 3)
    {
            if(deg[cr] > 3)
            {
                rus = 0;
                return ;
            }
            else
            {
                ruc = 1;
                inn[0] = cl;
            }
    }
    else         
    {
        if(gl != gr)
        {
            if(deg[cl] > 3)
            {
                if(deg[cr] > 3)
                {
                    rus = 0;
                    return ;
                }
                else
                {
                    ruc = 1;
                    inn[0] = cl;
                }
            }
            else if(deg[cl] == 3)
            {
                if(deg[cr] == 3)
                {
                    ruc = 2;
                    inn[0] = cl;
                    inn[1] = cr;
                }
                else 
                {
                    for(i=0; i<3; i++)
                    {
                        inn[i] = pat[cl][i];
                    }
                    inn[3] = cl;
                    ruc = 4;
                }
            }
            else 
            {
                return ;
            }
        }
        else 
        {
            if(deg[cl] == 3)
            {
                if(deg[cr] == 3)
                {
                    ruc = 2;
                    inn[0] = cl;
                    inn[1] = cr;
                    for(i=0; i<2; i++)
                    {
                        for(j=0; j<2; j++)
                        {
                            if(pat[cl][i] == pat[cr][j])
                            {
                                ruc = 3;
                                inn[2] = pat[cl][i];
                            }
                        }
                    }
                }
                else 
                {
                    for(i=0; i<3; i++)
                    {
                        thi[pat[cl][i]] = 1;
                    }
                    ocy = 0;
                    // inn[0] = cl;
                    ruc = 0;
                    of = 0;
                    re(cr,cl);
                    if(ocy == 1)
                    {
                        re(cl,cr);
                    }
                }
            }
            else 
            {
                // inn[0] = cr;
                ocy = 0;
                ruc = 0;
                of = 1;
                re(cr,cl);
                if(ocy == 1)
                {
                    inn[0] = ret;
                    ruc = 1;
                    re(cl,cr);
                    if(ret != inn[0])
                    {
                        inn[1] = ret;
                        ruc = 2;
                    }
                }
            }
        }
    }
    sort(inn,inn+ruc);
    cru = 0;
    cruc = 0;
    for(i=0; i<rus; i++)
    {
        while(cruc < ruc && see[i] > inn[cruc])
        {
            cruc ++;
        }
        if(cruc < ruc && see[i] == inn[cruc])
        {
            see[cru] = see[i];
            cru ++;
        }
    }
    rus = cru;
    return ;
}

int CountCritical()
{
    return rus;
}

Compilation message (stderr)

rings.cpp: In function 'int re(int, int)':
rings.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(i=0; i<pat[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~~
rings.cpp:41:11: warning: unused variable 'j' [-Wunused-variable]
   41 |     int i,j,fn,fou = 0,cva;
      |           ^
rings.cpp: In function 'void Init(int)':
rings.cpp:82:11: warning: unused variable 'j' [-Wunused-variable]
   82 |     int i,j;
      |           ^

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