제출 #65397

#제출 시각아이디문제언어결과실행 시간메모리
65397Bodo171낙하산 고리들 (IOI12_rings)C++14
55 / 100
3190 ms169964 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]; 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++)
                     ~^~~~~~~~~~~~
#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...