Submission #350697

#	Time	Username	Problem	Language	Result	Execution time	Memory
350697		Kerim	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	1774 ms	124436 KiB

rings

#include "bits/stdc++.h"
#define MAXN 1000009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
class dsu{
	public:
	int ata[MAXN],sz[MAXN];
	dsu(){}
	void init(int x){
		for(int i=1;i<=x;i++)
			ata[i]=i,sz[i]=1;	
	}
	int tap(int x){
		if(ata[x]==x)
			return x;
		return ata[x]=tap(ata[x]);	
	}
	void merge(int x,int y){
		if((x=tap(x))==(y=tap(y)))
			return;
		if(sz[x]>sz[y])
			swap(x,y);
		ata[y]=x;
		sz[x]+=sz[y];
	}
}D[5],T;
bool ok=0;
int H[5],Dg[5][MAXN],n,q,len_cycle=0;
int deg[MAXN],cycle=0,res[5];
vector<int>adj[MAXN];
void _add(int x,int y){
	for(int i=0;i<4;i++){
		if(!res[i])
			continue;
		if(H[i]==x or H[i]==y)
			continue;
		Dg[i][x]++;Dg[i][y]++;	
		if(Dg[i][x]==3 or Dg[i][y]==3){
			res[i]=0;
			continue;
		}
		if(D[i].tap(x)==D[i].tap(y)){
			res[i]=0;
			continue;
		}
		D[i].merge(x,y);
	}
}
void build(int x){
	ok=1;
	H[0]=x;
	H[1]=adj[x][0];
	H[2]=adj[x][1];
	H[3]=adj[x][2];
	for(int i=0;i<4;i++){
		D[i].init(n);
		res[i]=1;
	}
	for(int i=1;i<=n;i++)
		tr(it,adj[i])
			if(i<*it)
				_add(*it,i);
}
int dfs(int node,int nd,int pr,int num){
	if(node==nd and ~pr)
		return num;int mx=0;
	for(int i=0;i<int(adj[nd].size());i++){
		int to=adj[nd][i];
		if(to==pr)
			continue;
		umax(mx,dfs(node,to,nd,num+1));
	}
	return mx;
}
void Link(int x,int y){x++;y++;
	if(!ok){
		adj[x].pb(y);
		adj[y].pb(x);
		deg[x]++;deg[y]++;
		if(deg[x]==3){
			build(x);
			return;
		}
		if(deg[y]==3){
			build(y);
			return;
		}
		if(T.tap(x)==T.tap(y)){
			if(!cycle)
				len_cycle=dfs(x,x,-1,0);cycle++;	
			return;
		}
		T.merge(x,y);
	}
	else
		_add(x,y);
}
int CountCritical(){
	if(ok){
		int sum=0;
		for(int i=0;i<4;i++)sum+=res[i];
		return sum;	
	}
	if(!cycle)
		return n;
	if(cycle==1)
		return len_cycle;
	return 0;	
}
void Init(int szx){
	memset(deg,0,sizeof(deg));
	n=szx;T.init(szx);
}

Compilation message (stderr)

rings.cpp: In function 'int dfs(int, int, int, int)':
rings.cpp:79:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   79 |  if(node==nd and ~pr)
      |  ^~
rings.cpp:80:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   80 |   return num;int mx=0;
      |              ^~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:103:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  103 |    if(!cycle)
      |    ^~
rings.cpp:104:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  104 |     len_cycle=dfs(x,x,-1,0);cycle++;
      |                             ^~~~~

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