oj.uz

Submission #200930

# Submission time Handle Problem Language Result Execution time Memory
200930 2020-02-08T15:59:49 Z Lawliet Split the Attractions (IOI19_split) C++17
22 / 100
 1349 ms 1048580 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 )
	{
		qtd--;
		type[ cur ] = t;
	}

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

		if( viz == pai[cur] ) continue;
		if( viz == blocked ) 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 < p.size() ; 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:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < p.size() ; i++)
                  ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2680 KB ok, correct split
2 Runtime error 1349 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Runtime error 615 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 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 108 ms 10740 KB ok, correct split
3 Correct 34 ms 6012 KB ok, correct split
4 Correct 6 ms 2680 KB ok, correct split
5 Correct 115 ms 12660 KB ok, correct split
6 Correct 114 ms 12532 KB ok, correct split
7 Correct 112 ms 12400 KB ok, correct split
8 Correct 114 ms 13428 KB ok, correct split
9 Correct 113 ms 12148 KB ok, correct split
10 Correct 27 ms 5112 KB ok, no valid answer
11 Correct 39 ms 6432 KB ok, no valid answer
12 Correct 71 ms 10356 KB ok, no valid answer
13 Correct 80 ms 10232 KB ok, no valid answer
14 Correct 65 ms 10480 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 614 ms 1048580 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 7 ms 2680 KB ok, correct split
2 Runtime error 1349 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -