제출 #65397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65397		Bodo171	낙하산 고리들 (IOI12_rings)	C++14	55 / 100	3190 ms	169964 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];
int maimari,busit,mme,gradmx,speciale,nr,auxi;
struct dsu
{
    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(A==B) return;
        if(rg[A]>rg[B]) {tt[B]=A;rg[A]+=rg[B];}
        else {tt[A]=B;rg[B]+=rg[A];}
    }
};
struct linker
{
    dsu dsu1;
    int ciclu,wciclu,mxout,gr[nmax];
    void uneste(int x,int y)
    {
        gr[x]++;gr[y]++;
        if(gr[x]>mxout) mxout=gr[x];
        if(gr[y]>mxout) mxout=gr[y];
        if(dsu1.finds(x)==dsu1.finds(y))
            ciclu+=1,wciclu=dsu1.rg[dsu1.finds(x)];
        else dsu1.unite(dsu1.finds(x),dsu1.finds(y));
    }
}li[7],aux[10];
void rezolva(int x)
{
    if(grad[x]>=3||(valid[x])) return;
    for(int i=0;i<v[x].size();i++)
            if(grad[v[x][i]]==3)
        {
            valid[x]=1;
        }
    if(!valid[x]) return;
    auxi++;
    auxiliare[auxi]=x;
    aux[auxi].dsu1.ini();
    for(int i=1;i<=nr;i++)
        if(muchii[i].first!=x&&muchii[i].second!=x)
            aux[auxi].uneste(muchii[i].first,muchii[i].second);
}
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]==gradmx)
        {
            speciale++;
        }
        else
        {
            speciale=1;
            gradmx=grad[x];
        }
        nodspecial[speciale]=x;
         li[speciale].dsu1.ini();
         if(special[x]!=speciale)
         {
         li[speciale].mxout=0;li[speciale].ciclu=0;li[speciale].wciclu=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;
         }
    }
    if(gradmx==3&&speciale>4)
    {
        busit=1;
    }
      if(gradmx==3&&speciale<3)
    {
        for(int i=0;i<v[x].size();i++)
            rezolva(v[x][i]);
    }
}
void Init(int N_) {

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

}

void Link(int A, int B) {
    if(busit) return;

    grad[A]++;
    grad[B]++;
    v[A].push_back(B);
    v[B].push_back(A);
    spec(A);
    spec(B);
    muchii[++nr]={A,B};
    for(int i=0;i<=speciale;i++)
        if(i==0||(nodspecial[i]!=A&&nodspecial[i]!=B))
           li[i].uneste(A,B);
    if(gradmx==3&&speciale<=2)
        for(int i=1;i<=auxi;i++)
          if(auxiliare[i]!=A&&auxiliare[i]!=B)
              aux[i].uneste(A,B);
}

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++;
  }
  if(gradmx==3&&speciale<=2)
  {
      for(int i=1;i<=auxi;i++)
        if((!aux[i].ciclu)&&aux[i].mxout<3&&(!special[auxiliare[i]]))
             ret++;
  }
  if(ret==0) busit=1;
  return ret;

}

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

rings.cpp: In function 'void rezolva(int)':
rings.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
rings.cpp: In function 'void spec(int)':
rings.cpp:108:22: 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: 0 / 14
• Subtask 5: 0 / 31