Submission #1272227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272227		thunopro	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	102 ms	26152 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

int n , ma , vis [maxn] ; 
vi block ,edge , circle ;
vector<vi> graph,res ;

void add_edge ( int u , int v ) { res [u][v] = res [v][u] = 1 ; } 
void dfs ( int u ) 
{
	vis [u] = 1 ; 
	block.pb (u) ; 
	for ( int v = 0 ; v < n ; v ++ ) 
	{
		ma = max (ma,graph[u][v]) ; 
		if ( !vis [v] && graph [u][v] ) dfs (v) ; 
	}
}

void dfsCircle ( int u ) 
{
	vis [u] = 2 ; 
	edge.pb (u) ; 
	for ( int v = 0 ; v < n ; v ++ ) if ( vis [v] == 1 && graph [u][v] == 1 ) dfsCircle (v) ; 
}
int construct( vector<vi> p ) {
	graph = p , n = p.size () ; res.resize (n) ; 
	for ( int i = 0 ; i < n ; i ++ ) res [i].resize (n) ; 
	for ( int i = 0 ; i < n ; i ++ ) 
	{
		if ( vis [i] ) continue ; 
		ma = 1 ; block.clear() ; dfs (i) ; 
		if ( ma == 3 ) return 0 ; 
		int sz = block.size () ; 
		for ( int j = 1 ; j < sz ; j ++ ) 
		{
			for ( int k = 0 ; k < j ; k ++ ) 
			{
				if ( !graph[block[j]][block[k]] ) return 0 ; 
			}
		}
		if ( ma == 1 ) for ( int j = 1 ; j < sz ; j ++ ) add_edge (block[0],block[j]) ; 
		else 
		{
			circle.clear() ; 
			for ( int r = 0 , j = block [r] ; r < sz ; r ++ , j = block [r] ) 
			{
				if ( vis [j] != 1 ) continue ; 
				edge.clear() ; 
				dfsCircle (j) ; 
				int sz2 = edge.size() ; 
				for ( int k = 1 ; k < sz2 ; k ++ ) 
				{
					for ( int l = 0 ; l < k ; l ++ ) 
					{
						if ( graph[edge[k]][edge[l]] != 1 ) return 0 ; 
					}
					add_edge (edge[0],edge[k]) ; 
				}
				circle.pb(edge[0]) ; 
			}
			if ( circle.size () <= 2 ) return 0 ; 
			int sz3 = circle.size () ; 
			for ( int j = 0 ; j < sz3 ; j ++ ) add_edge (circle[j],circle[(j+1)%sz3]) ; 
		}
	}
	build (res) ; 
	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