oj.uz

Submission #219975

# Submission time Handle Problem Language Result Execution time Memory
219975 2020-04-06T18:40:10 Z Lawliet Parachute rings (IOI12_rings) C++14
100 / 100
 1753 ms 131280 KB 
#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)
		{
			for(int i = 1 ; i <= n ; i++)
			{
				sz[i] = 1;
				pai[i] = i;
			}
		}

	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( cycles.same( A , B ) && adj[A].size() == 2 )
		{
			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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 21 ms 24448 KB Output is correct
3 Correct 21 ms 24544 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 23 ms 24576 KB Output is correct
10 Correct 21 ms 24576 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 49372 KB Output is correct
2 Correct 1197 ms 99860 KB Output is correct
3 Correct 1030 ms 114384 KB Output is correct
4 Correct 1095 ms 71760 KB Output is correct
5 Correct 1132 ms 84432 KB Output is correct
6 Correct 1071 ms 82576 KB Output is correct
7 Correct 992 ms 124952 KB Output is correct
8 Correct 1606 ms 124368 KB Output is correct
9 Correct 1753 ms 131280 KB Output is correct
10 Correct 845 ms 81304 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 21 ms 24448 KB Output is correct
3 Correct 21 ms 24544 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 23 ms 24576 KB Output is correct
10 Correct 21 ms 24576 KB Output is correct
11 Correct 21 ms 24448 KB Output is correct
12 Correct 24 ms 24960 KB Output is correct
13 Correct 24 ms 25088 KB Output is correct
14 Correct 22 ms 24832 KB Output is correct
15 Correct 23 ms 25344 KB Output is correct
16 Correct 24 ms 24448 KB Output is correct
17 Correct 23 ms 24960 KB Output is correct
18 Correct 25 ms 25728 KB Output is correct
19 Correct 23 ms 24448 KB Output is correct
20 Correct 24 ms 25088 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 21 ms 24448 KB Output is correct
3 Correct 21 ms 24544 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 23 ms 24576 KB Output is correct
10 Correct 21 ms 24576 KB Output is correct
11 Correct 21 ms 24448 KB Output is correct
12 Correct 24 ms 24960 KB Output is correct
13 Correct 24 ms 25088 KB Output is correct
14 Correct 22 ms 24832 KB Output is correct
15 Correct 23 ms 25344 KB Output is correct
16 Correct 24 ms 24448 KB Output is correct
17 Correct 23 ms 24960 KB Output is correct
18 Correct 25 ms 25728 KB Output is correct
19 Correct 23 ms 24448 KB Output is correct
20 Correct 24 ms 25088 KB Output is correct
21 Correct 38 ms 25852 KB Output is correct
22 Correct 54 ms 27120 KB Output is correct
23 Correct 61 ms 27888 KB Output is correct
24 Correct 66 ms 31728 KB Output is correct
25 Correct 36 ms 29944 KB Output is correct
26 Correct 67 ms 32624 KB Output is correct
27 Correct 71 ms 28912 KB Output is correct
28 Correct 69 ms 33260 KB Output is correct
29 Correct 57 ms 31860 KB Output is correct
30 Correct 79 ms 29672 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 21 ms 24448 KB Output is correct
3 Correct 21 ms 24544 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24192 KB Output is correct
7 Correct 19 ms 24192 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 23 ms 24576 KB Output is correct
10 Correct 21 ms 24576 KB Output is correct
11 Correct 439 ms 49372 KB Output is correct
12 Correct 1197 ms 99860 KB Output is correct
13 Correct 1030 ms 114384 KB Output is correct
14 Correct 1095 ms 71760 KB Output is correct
15 Correct 1132 ms 84432 KB Output is correct
16 Correct 1071 ms 82576 KB Output is correct
17 Correct 992 ms 124952 KB Output is correct
18 Correct 1606 ms 124368 KB Output is correct
19 Correct 1753 ms 131280 KB Output is correct
20 Correct 845 ms 81304 KB Output is correct
21 Correct 21 ms 24448 KB Output is correct
22 Correct 24 ms 24960 KB Output is correct
23 Correct 24 ms 25088 KB Output is correct
24 Correct 22 ms 24832 KB Output is correct
25 Correct 23 ms 25344 KB Output is correct
26 Correct 24 ms 24448 KB Output is correct
27 Correct 23 ms 24960 KB Output is correct
28 Correct 25 ms 25728 KB Output is correct
29 Correct 23 ms 24448 KB Output is correct
30 Correct 24 ms 25088 KB Output is correct
31 Correct 38 ms 25852 KB Output is correct
32 Correct 54 ms 27120 KB Output is correct
33 Correct 61 ms 27888 KB Output is correct
34 Correct 66 ms 31728 KB Output is correct
35 Correct 36 ms 29944 KB Output is correct
36 Correct 67 ms 32624 KB Output is correct
37 Correct 71 ms 28912 KB Output is correct
38 Correct 69 ms 33260 KB Output is correct
39 Correct 57 ms 31860 KB Output is correct
40 Correct 79 ms 29672 KB Output is correct
41 Correct 250 ms 41620 KB Output is correct
42 Correct 757 ms 96092 KB Output is correct
43 Correct 294 ms 82160 KB Output is correct
44 Correct 835 ms 121620 KB Output is correct
45 Correct 862 ms 113888 KB Output is correct
46 Correct 773 ms 74228 KB Output is correct
47 Correct 934 ms 75736 KB Output is correct
48 Correct 545 ms 104156 KB Output is correct
49 Correct 749 ms 73172 KB Output is correct
50 Correct 788 ms 72924 KB Output is correct
51 Correct 336 ms 77164 KB Output is correct
52 Correct 692 ms 102992 KB Output is correct
53 Correct 526 ms 104796 KB Output is correct
54 Correct 1382 ms 111368 KB Output is correct
55 Correct 1223 ms 118864 KB Output is correct