Submission #200941

#	Time	Username	Problem	Language	Result	Execution time	Memory
200941		Lawliet	Split the Attractions (IOI19_split)	C++17	11 / 100	140 ms	18036 KiB

split

#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 (stderr)

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
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36