제출 #66000

#제출 시각아이디문제언어결과실행 시간메모리
66000Bodo171낙하산 고리들 (IOI12_rings)C++14
100 / 100
1503 ms110444 KiB
#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++)
                             ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...