제출 #66000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66000		Bodo171	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	1503 ms	110444 KiB

rings

#include <iostream>
#include <vector>

using namespace std;
const int nmax=1000*1000+5;
int n;
pair<int,int> muchii[nmax];
vector<int> v[nmax];
int grad[nmax],special[nmax],valid[nmax];
int nodspecial[10],auxiliare[10],ab[10],abaux[10];
int maimari,busit,mme,gradmx,speciale,nr,auxi,eq3;
struct linker
{
    int ciclu,wciclu,mxout;
    char gr[nmax];
    int tt[nmax],rg[nmax];
    void ini()
    {
        for(int i=0;i<n;i++)
            tt[i]=i,rg[i]=1;
    }
    int finds(int x)
    {
        int y=x,aux=0;
        while(x!=tt[x])
            x=tt[x];
        while(y!=x)
        {
            aux=tt[y];
            tt[y]=x;
            y=aux;
        }
        return x;
    }
    void unite(int A,int B)
    {
        if(rg[A]>rg[B]) {tt[B]=A;rg[A]+=rg[B];}
        else {tt[A]=B;rg[B]+=rg[A];}
    }
    void uneste(int x,int y)
    {
        gr[x]++;gr[y]++;
        if(gr[x]>mxout) mxout=(int)gr[x];
        if(gr[y]>mxout) mxout=(int)gr[y];
        if(finds(x)==finds(y))
            ciclu+=1,wciclu=rg[finds(x)];
        else unite(finds(x),finds(y));
    }
}li[5];
void specialul(int x)
{
    speciale++;nodspecial[speciale]=x;
     ab[speciale]=0;
     li[speciale].mxout=0;li[speciale].ciclu=0;li[speciale].wciclu=0;
     li[speciale].ini();
    for(int i=0;i<n;i++)
        li[speciale].gr[i]=0;
    for(int i=1;i<=nr;i++)
        if(muchii[i].first!=x&&muchii[i].second!=x)
            li[speciale].uneste(muchii[i].first,muchii[i].second);
    special[x]=speciale;
}
void spec(int x)
{
    if(grad[x]==4)
    {
        maimari++;
        if(maimari>1)
        {
            busit=1;
            return;
        }
    }
    if(grad[x]>=gradmx&&grad[x]>=3)
    {
        if(grad[x]==3)
        {
            gradmx=3;eq3++;
            if(eq3>4) busit=1;
            if(!speciale)
            {
                specialul(x);
                for(int i=0;i<v[x].size();i++)
                    specialul(v[x][i]);
            }
            return;
        }
        else
        {
            gradmx=grad[x];
            if(grad[x]>3)
            {
                if(speciale!=special[x])
                {
                    speciale=0;
                    specialul(x);
                }
            }
        }
    }
}
void Init(int N_) {

  n = N_;
  li[0].ini();

}

void Link(int A, int B) {
    if(busit) return;
    grad[A]++;
    grad[B]++;
    if(gradmx<3)
    {
     v[A].push_back(B);
     v[B].push_back(A);
    }
    spec(A);
    spec(B);
    muchii[++nr]={A,B};
    for(int i=(speciale!=0);i<=speciale;i++)
        if((!ab[i]))
        if(i==0||(nodspecial[i]!=A&&nodspecial[i]!=B))
           li[i].uneste(A,B);
    for(int i=1;i<=speciale;i++)
        if(li[i].mxout>=3||li[i].ciclu)
          ab[i]=1;
}

int CountCritical() {
  if(busit)
  {
      return 0;
  }
  if(gradmx<3)
  {
      if(li[0].ciclu>1)
      {
          busit=1;
          return 0;
      }
      if(li[0].ciclu==1)
        return li[0].wciclu;
      return n;
  }
  int ret=0;
  for(int i=1;i<=speciale;i++)
  {
    if((!li[i].ciclu)&&li[i].mxout<3) ret++;
    else ab[i]=1;
  }
  if(ret==0) busit=1;
  return ret;

}

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'void spec(int)':
rings.cpp:83:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0;i<v[x].size();i++)
                             ~^~~~~~~~~~~~

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