oj.uz

Submission #200941

# Submission time Handle Problem Language Result Execution time Memory
200941 2020-02-08T18:20:46 Z Lawliet Split the Attractions (IOI19_split) C++17
11 / 100
 140 ms 18036 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;

const int MAXN = 100010;

int n;
int curT;

int tin[MAXN];
int low[MAXN];
int type[MAXN];

bool marc[MAXN];
bool isCutVertex[MAXN];

vector< int > ans;

vector< int > adj[MAXN];

void DFSLowlink(int cur, int p)
{
	low[cur] = tin[cur] = ++curT;

	bool hasPath = false;

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

		if( viz == p ) continue;

		if( tin[viz] != 0 )
		{
			low[cur] = min( low[cur] , tin[viz] );
			continue;
		}

		DFSLowlink( viz , cur );

		if( (cur == 0) ? hasPath : (low[viz] >= tin[cur]) ) isCutVertex[cur] = true;

		hasPath = true;

		low[cur] = min( low[cur] , low[viz] );
	}
}

void findAnswer(int cur, int& qtd, int t)
{
	if( qtd == 0 ) return;
 
	qtd--;
	type[ cur ] = t;
	marc[ cur ] = true;
 
	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( marc[viz] ) continue;
 
		findAnswer( viz , qtd , t );
	}
}

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] );
	}

	DFSLowlink( 0 , 0 );

	int root = 0;

	for(int i = 0 ; i < n ; i++)
		if( !isCutVertex[i] ) root = i;

	assert( !isCutVertex[root] );

	type[ root ] = 1;
	marc[ root ] = true;

	int other = 0;
	if( root == 0 ) other = 1;

	findAnswer( other , b , 2 );

	for(int i = 0 ; i < n ; i++)
	{
		if( type[i] == 0 ) ans.push_back( 3 );
		else ans.push_back( type[i] );
	}

	return ans;
}

Compilation message

split.cpp: In function 'void DFSLowlink(int, int)':
split.cpp:28: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)':
split.cpp:58: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:72: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 6 ms 2680 KB ok, correct split
2 Correct 6 ms 2680 KB ok, correct split
3 Correct 6 ms 2680 KB ok, correct split
4 Incorrect 6 ms 2680 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB ok, correct split
2 Correct 7 ms 2680 KB ok, correct split
3 Correct 6 ms 2552 KB ok, correct split
4 Correct 117 ms 15600 KB ok, correct split
5 Correct 87 ms 10868 KB ok, correct split
6 Correct 96 ms 18036 KB ok, correct split
7 Correct 119 ms 15732 KB ok, correct split
8 Correct 140 ms 14196 KB ok, correct split
9 Correct 100 ms 10872 KB ok, correct split
10 Correct 60 ms 10604 KB ok, correct split
11 Correct 60 ms 10736 KB ok, correct split
12 Correct 65 ms 11120 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2680 KB invalid split: #1=1, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2684 KB invalid split: #1=1, #2=2, #3=6
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 2680 KB ok, correct split
4 Incorrect 6 ms 2680 KB invalid split: #1=1, #2=1, #3=2
5 Halted 0 ms 0 KB -