oj.uz

Submission #200931

# Submission time Handle Problem Language Result Execution time Memory
200931 2020-02-08T16:04:13 Z Lawliet Split the Attractions (IOI19_split) C++17
29 / 100
 591 ms 1048576 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;

const int MAXN = 100010;

int n;

int pai[MAXN];
int sub[MAXN];
int type[MAXN];

vector< int > ans;

vector< int > adj[MAXN];

void DFS(int cur, int p)
{
	sub[cur] = 1;
	pai[cur] = p;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		DFS( viz , cur );

		sub[ cur ] += sub[ viz ];
	}
}

void findAnswer(int cur, int blocked, int& qtd, int t)
{
	if( qtd == 0 ) return;

	qtd--;
	type[ cur ] = t;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == blocked ) continue;
		if( viz == pai[cur] ) continue;

		findAnswer( viz , blocked , qtd , t );
	}
}

void tryAnswer(int A, int tA, int B, int tB)
{
	if( ans.size() > 0 ) return;

	bool find = false;

	for(int i = 1 ; i < n && !find ; i++)
	{
		int other = n - sub[i];

		if( sub[i] >= A && other >= B )
		{
			find = true;

			findAnswer( 0 , i , B , tB );
			findAnswer( i , pai[i] , A , tA );			
		}
	}

	if( !find ) return;

	for(int i = 0 ; i < n ; i++)
	{
		if( type[i] != 0 ) ans.push_back( type[i] );
		else ans.push_back( 6 - tA - tB );
	}
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) 
{
	n = N;

	for(int i = 0 ; i < N - 1 ; i++)
	{
		adj[ p[i] ].push_back( q[i] );
		adj[ q[i] ].push_back( p[i] );
	}

	DFS( 0 , 0 );

	tryAnswer( a , 1 , b , 2 );
	tryAnswer( a , 1 , c , 3 );
	tryAnswer( b , 2 , a , 1 );
	tryAnswer( b , 2 , c , 3 );
	tryAnswer( c , 3 , a , 1 );
	tryAnswer( c , 3 , b , 2 );

	if( ans.size() == 0 ) ans.resize( n , 0 );

	return ans;
}

Compilation message

split.cpp: In function 'void DFS(int, int)':
split.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void findAnswer(int, int, int&, int)':
split.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Correct 6 ms 2680 KB ok, correct split
3 Correct 6 ms 2808 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 6 ms 2680 KB ok, correct split
6 Correct 6 ms 2680 KB ok, correct split
7 Correct 105 ms 16628 KB ok, correct split
8 Correct 112 ms 14708 KB ok, correct split
9 Correct 113 ms 14196 KB ok, correct split
10 Correct 101 ms 16244 KB ok, correct split
11 Correct 106 ms 15604 KB ok, correct split

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Correct 6 ms 2684 KB ok, correct split
3 Incorrect 6 ms 2680 KB jury found a solution, contestant did not
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Correct 89 ms 10608 KB ok, correct split
3 Correct 31 ms 6008 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 107 ms 12532 KB ok, correct split
6 Correct 112 ms 12532 KB ok, correct split
7 Correct 108 ms 12276 KB ok, correct split
8 Correct 106 ms 13300 KB ok, correct split
9 Correct 133 ms 12148 KB ok, correct split
10 Correct 27 ms 5240 KB ok, no valid answer
11 Correct 38 ms 6392 KB ok, no valid answer
12 Correct 85 ms 10356 KB ok, no valid answer
13 Correct 82 ms 10104 KB ok, no valid answer
14 Correct 63 ms 10352 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 591 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Correct 6 ms 2680 KB ok, correct split
3 Correct 6 ms 2808 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 6 ms 2680 KB ok, correct split
6 Correct 6 ms 2680 KB ok, correct split
7 Correct 105 ms 16628 KB ok, correct split
8 Correct 112 ms 14708 KB ok, correct split
9 Correct 113 ms 14196 KB ok, correct split
10 Correct 101 ms 16244 KB ok, correct split
11 Correct 106 ms 15604 KB ok, correct split
12 Correct 6 ms 2680 KB ok, correct split
13 Correct 6 ms 2684 KB ok, correct split
14 Incorrect 6 ms 2680 KB jury found a solution, contestant did not
15 Halted 0 ms 0 KB -