Submission #306146

#	Time	Username	Problem	Language	Result	Execution time	Memory
306146		CaroLinda	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	265 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size() )

const int MAXN = 1010 ;

using namespace std ;

int pai[MAXN] ;

int find(int x )
{
	if( x == pai[x] ) return x ;
	return pai[x] = find(pai[x] ) ;
}

void join(int x, int y )
{

	x = find(x) ;
	y = find(y) ;

	if(x == y ) return ;

	if(rand() % 2 ) pai[x] = y ;
	else pai[y] = x ;

}

int construct( vector< vector<int> > p ) {

	int n = sz(p) ;

	for(auto i : p )
		for(auto j : i )
			if( j == 3 ) return 0 ;

	vector< vector<int> > componentes(n, vector<int>() ) ;
	vector< vector<int> > graph(n, vector<int>(n,0) ) ;

	for(int i  =0  ; i < n ; i++ ) pai[i] = i ;

	for(int i = 0 ; i < n ; i++ )
		for(int j = 0 ; j < n ; j++ )
			if(p[i][j] ) join(i,j) ;

	for(int i = 0 ; i < n ; i++ )
		componentes[ find(i) ].push_back(i) ;

	vector< vector<int> > tree(n, vector<int>() ) ;

	for(int i = 0 ; i < n ; i++ ) pai[i] = i ;

	for(int i = 0 ; i < n ; i++ )
	{
		for(int j1 : componentes[i] )
			for(int j2 : componentes[i] )
			{
				if( p[j1][j2] == 0 )  return 0 ;
				if(p[j1][j2] == 1 ) join(j1,j2) ; 
			}

		vector<int> cycle ;

		for(int j : componentes[i] )
		{
			tree[find(j)].push_back(j) ;
			if(find(j) == j ) cycle.push_back(j) ;
		}

		if(sz(cycle) == 2 ) return  0 ;
		if(sz(cycle) == 1 ) continue ;

		for(int j = 0 , nxt = 1 ; j < sz(cycle) ; j++ , nxt++ )
		{
			if(nxt == sz(cycle) ) nxt = 0 ;

			graph[ cycle[j] ][ cycle[nxt] ]  = graph[ cycle[nxt] ][ cycle[j] ] = 1 ;

		}
		
	}

	for(int i = 0 ; i < n ; i++ )
	{

		if( sz(tree[i]) == 0 ) continue ;

	  int rep = tree[i][0] ;

	  for(int j = 1 ; j < sz(tree[i] ) ; j++ ) graph[rep][tree[i][j]] = graph[ tree[i][j] ][rep] = 1 ;

	}

	build(graph) ;

	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4