| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 62572 | zetapi | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e6+99;
vector<int> vec[MAX];
int linear[4],destruct[4],deg[4][MAX],OtherEnd[4][MAX];
int N,cnt,CycleSize,Quad,a,b;
void Init(int N_)
{
N=N_;
cnt=0;
Quad=0;
CycleSize=0;
for(int A=0;A<N;A++)
{
deg[0][A]=0;
OtherEnd[0][A]=A;
vec[A].clear();
}
return ;
}
void Add(int X,int Y)
{
for(int A=0;A<4;A++)
{
if(!linear[A] or destruct[A]==X or destruct[A]==Y)
continue;
deg[A][X]++;
deg[A][Y]++;
if(deg[A][X]==3 or deg[A][Y]==3 or OtherEnd[A][X]==Y)
{
linear[A]=0;
continue;
}
a=OtherEnd[A][X];
b=OtherEnd[A][Y];
OtherEnd[A][X]=-1;
OtherEnd[A][Y]=-1;
OtherEnd[A][a]=b;
OtherEnd[A][b]=a;
}
return ;
}
void Split(int X)
{
Quad=1;
destruct[0]=X;
destruct[1]=vec[X][0];
destruct[2]=vec[X][1];
destruct[3]=vec[X][2];
for(int A=0;A<4;A++)
{
linear[A]=1;
for(int B=0;B<N;B++)
{
deg[A][B]=0;
OtherEnd[A][B]=B;
}
}
for(int A=0;A<N;A++)
for(auto B:vec[A])
if(A<B)
Add(A,B);
return ;
}
void Link(int X,int Y)
{
if(Quad==0)
{
vec[X].pb(Y);
vec[Y].pb(X);
deg[0][X]++;
deg[0][Y]++;
if(deg[0][X]==3)
{
Split(X);
return ;
}
if(deg[0][Y]==3)
{
Split(Y);
return ;
}
if(OtherEnd[0][X]!=Y)
{
a=OtherEnd[0][X];
b=OtherEnd[0][Y];
OtherEnd[0][X]=-1;
OtherEnd[0][Y]=-1;
OtherEnd[0][a]=b;
OtherEnd[0][b]=a;
return ;
}
cnt++;
if(cnt==1)
{
int cur=X,pre=X;
do
{
CycleSize++;
if(vec[cur][0]==pre)
{
pre=cur;
cur=vec[cur][1];
}
else
{
pre=cur;
cur=vec[cur][0];
}
}
while(cur!=X);
}
}
else
Add(X,Y);
return ;
}
int CountCritical()
{
if(!Quad)
{
if(cnt>1)
return 0;
else if(CycleSize)
return CycleSize;
else
return N;
}
else
return (linear[0]+linear[1]+linear[2]+linear[3]);
}