Submission #121175

#	Time	Username	Problem	Language	Result	Execution time	Memory
121175		baluteshih	Parachute rings (IOI12_rings)	C++14	100 / 100	3434 ms	103864 KiB

rings

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int C=5;
int N,boss[5][1000005],upd,tag[1000005],flag,flag2,ans[C],sz[C][1000005],cir;
vector<int> G[1000005],pos;

void Init(int N_)
{
	N=N_;
	for(int j=0;j<4;++j)
		ans[j]=1;
	for(int i=0;i<N;++i)
		for(int j=0;j<C;++j)
			boss[j][i]=i;
}

int finds(int t,int a)
{
	if(boss[t][a]==a) return a;
	return boss[t][a]=finds(t,boss[t][a]);
}

bool Union(int t,int a,int b)
{
	a=finds(t,a),b=finds(t,b);
	if(a==b) return 0;
	boss[t][a]=b;
	return 1;
}

void update(int x)
{
	++upd,pos.pb(x);
	for(int i:G[x])
		pos.pb(i);
	for(int i=0;i<pos.size();++i)
	{
		for(int j=0;j<N;++j)
			if(j!=pos[i])	
				for(int k:G[j])
					if(k!=pos[i]&&j<k)
						ans[i]&=Union(i,j,k),++sz[i][j],++sz[i][k];
		for(int j=0;j<N;++j)
			if(j!=pos[i])
				ans[i]&=(sz[i][j]<3);
	}
}

void add_edge(int a,int b)
{
	for(int i=0;i<4;++i)
		if(a!=pos[i]&&b!=pos[i])
		{
			ans[i]&=Union(i,a,b);
			++sz[i][a],++sz[i][b];
			ans[i]&=(sz[i][a]<3),ans[i]&=(sz[i][b]<3);
		}
}

void Link(int A, int B)
{
	G[A].pb(B),G[B].pb(A);
	if(flag) add_edge(A,B);
	if(!flag&&G[A].size()==3) flag=1,update(A);
	if(!flag&&G[B].size()==3) flag=1,update(B);
	if(!flag)
		if(!Union(4,A,B))
			if(!flag2)
				for(int i=(flag2=1,0);i<N;++i)
					cir+=(finds(4,i)==finds(4,A));
			else
				cir=0;
}

int CountCritical()
{
	if(flag) return ans[0]+ans[1]+ans[2]+ans[3];
	if(flag2) return cir;
	return N;
}

Compilation message (stderr)

rings.cpp: In function 'void update(int)':
rings.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size();++i)
              ~^~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:80:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   if(!Union(4,A,B))
     ^

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