Submission #219963

#	Time	Username	Problem	Language	Result	Execution time	Memory
219963		Lawliet	Parachute rings (IOI12_rings)	C++14	0 / 100	1119 ms	126164 KiB

rings

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 1000010;

class UnionFind
{
	public:

		int find(int cur)
		{
			if( pai[cur] == cur ) return cur;
			return pai[cur] = find( pai[cur] );
		}

		int getSize(int U) { return sz[ find(U) ]; }

		bool same(int U, int V) { return find(U) == find(V); }

		void join(int U, int V)
		{
			U = find( U ); V = find( V );

			if( U == V ) return;

			if( sz[U] < sz[V] ) swap( U , V );

			pai[V] = U;
			sz[U] += sz[V];
		}

		void init(int n)
		{
			memset( sz , 1 , sizeof(sz) );
			iota( pai + 1 , pai + n + 1 , 1 );
		}

	private:

		int sz[MAXN];
		int pai[MAXN];
};

class Forest
{
	public:

		void addEdge(int U, int V)
		{
			if( !valid ) return;

			if( U == root ) return;
			if( V == root ) return;

			degree[U]++;
			degree[V]++;

			if( degree[U] >= 3 ) valid = false;
			if( degree[V] >= 3 ) valid = false;
			if( DSU.same( U , V ) ) valid = false;

			DSU.join( U , V );
		}

		bool isValid() { return valid; }

		void init(int n, int r)
		{
			root = r;
			valid = true;

			for(int i = 1 ; i <= n ; i++)
				degree[i] = 0;

			DSU.init( n );
		}

	private:

		bool valid;

		int root;

		int degree[MAXN];

		UnionFind DSU;
};


int n;
int qtdCycles; 
int maxDegree;
int nodeCycles;
int qtdCritical;

vector< int > adj[MAXN];

vector< pii > edges;

UnionFind cycles;

Forest paths[5];

void Init(int N_)
{
	n = qtdCritical = N_;
	cycles.init( n );
}

void createForest(int node, int ind)
{
	paths[ind].init( n , node );

	for(int i = 0 ; i < edges.size() ; i++)
	{
		int U = edges[i].first;
		int V = edges[i].second;

		paths[ind].addEdge( U , V );
	}
}

void Link(int A, int B) 
{
	A++; B++;
	if( qtdCritical == 0 ) return;

	if( adj[A].size() > adj[B].size() ) swap( A , B );

	if( maxDegree >= 3 )
	{
		int qtd = 1;
		if( maxDegree == 3 ) qtd = 4;

		for(int j = 0 ; j < qtd ; j++)
			paths[j].addEdge( A , B );
	}

	adj[A].push_back( B );
	adj[B].push_back( A );

	edges.push_back( { A , B } );

	int oldMaxDegree = maxDegree;

	maxDegree = max( maxDegree , (int)adj[A].size() );
	maxDegree = max( maxDegree , (int)adj[B].size() );

	if( maxDegree == 2 )
	{
		if( adj[A].size() == 1 ) return;

		if( cycles.same( A , B ) )
		{
			qtdCycles++;

			if( qtdCycles > 1 )
			{
				qtdCritical = 0;
				return;
			}

			qtdCritical = cycles.getSize( A );
		}
	}	

	if( oldMaxDegree == 2 && maxDegree == 3 )
	{
		createForest( B , 0 );

		for(int i = 0 ; i < 3 ; i++)
			createForest( adj[B][i] , i + 1 );
	}

	if( oldMaxDegree == 3 && maxDegree == 4 )
		createForest( B , 0 );

	cycles.join( A , B );
}

int CountCritical()
{
	if( maxDegree <= 2 ) return qtdCritical;

	int ans = 0;
	int qtd = 1;
	if( maxDegree == 3 ) qtd = 4;

	for(int i = 0 ; i < qtd ; i++)
		if( paths[i].isValid() ) ans++;

	return ans;
}

Compilation message (stderr)

rings.cpp: In function 'void createForest(int, int)':
rings.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < edges.size() ; i++)
                  ~~^~~~~~~~~~~~~~

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