Submission #333853

#	Time	Username	Problem	Language	Result	Execution time	Memory
333853		CaroLinda	Meetings (JOI19_meetings)	C++14	100 / 100	1973 ms	1144 KiB

meetings

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

#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long

using namespace std ;

int qtd ;
vector<int> sub , arr ;
vector<bool> vis , foundPlace ;
vector< vector<int> > adj ;

void dfs1(int x, int parent)
{
	sub[x] = 1 ;

	for(auto e : adj[x] )
	{
		if(vis[e] || e == parent ) continue ;

		dfs1(e, x ) ;
		sub[x] += sub[e] ;

	}

}

int dfs2(int x, int parent )
{
	for(auto e : adj[x] )
	{
		if( e == parent || vis[e] ) continue ;
		if( sub[e] > qtd/2 ) return dfs2(e, x ) ;
	}
	return x ;
}

void dfs3(int x, int parent )
{
	sub[x] = 1 ;

	for(auto e : adj[x] )
	{
		if( e == parent || vis[e] ) continue ;
		dfs3(e,x ) ;
		sub[x] += sub[e] ;
	}

}

void insertMiddle(int A, int middle, int B )
{

	for(int i = 0 ; i < 2 ; i++ )
	{
		for(int j = 0 ; j < sz(adj[A]) ; j++ )
		{
			if( adj[A][j] != B ) continue ;
		
			swap(adj[A][ sz( adj[A] )-1 ], adj[A][j] ) ;
			adj[A].pop_back() ;

			break ;
		}

		swap(A,B) ;
	}

	adj[A].push_back(middle) ;
	adj[B].push_back(middle) ;

	adj[middle].push_back(A) ;
	adj[middle].push_back(B) ;

}

void createEdge(int A, int B )
{
	adj[A].push_back(B) ;
	adj[B].push_back(A) ;
}

void decompose( int toInsert , int x )
{

	dfs1( x , -1 ) ;

	qtd = sub[x] ;
	
	int cn = dfs2(x,-1) ;

	dfs3(cn,-1) ;

	vector<int> children ;

	for(auto e : adj[cn] ) 
		if( !vis[e] ) children.push_back( e ) ;

	sort(all(children), [&](int i, int j ) { return sub[i] < sub[j] ; } ) ;

	vis[cn] = true ;

	for(int i = 0 ; i < sz(children) ; i += 2 )
	{
		if(i+1 == sz(children) )
		{
			int resp = Query(children[i], toInsert, cn ) ;

			if( resp == toInsert ) insertMiddle(children[i], toInsert, cn ) ;
			else if( resp == cn ) createEdge(cn, toInsert) ;
			else if( resp == children[i] ) decompose(toInsert, children[i] ) ;			
			else
			{
				insertMiddle(cn, resp, children[i] ) ;
				createEdge(resp, toInsert) ;

				foundPlace[resp] = true ;

			}

			return ;

		}

		int resp = Query(children[i], children[i+1], toInsert) ;

		if(resp == cn ) continue ;		
		else if( resp == children[i] ) return (void)(decompose(toInsert, children[i] ) ) ;
		else if( resp == children[i+1] ) return (void)(decompose(toInsert, children[i+1] ) ) ;
		else if( resp == toInsert )
		{
			resp = Query( children[i] , cn , toInsert ) ;

			if( resp == toInsert ) insertMiddle( children[i] , toInsert, cn ) ;
			else insertMiddle(children[i+1], toInsert, cn ) ;

			return ;

		}
		else
		{
			int resp2 = Query(children[i], cn, resp ) ;

			if(resp2 == resp )
			{
				insertMiddle(children[i], resp, cn ) ;
				createEdge(resp, toInsert) ;
				foundPlace[ resp ]= true ;
			}
			else 
			{
				insertMiddle(children[i+1], resp, cn ) ;
				createEdge(resp, toInsert) ;
				foundPlace[resp] = true ;
			}

			return ;

		}
	}

	createEdge(cn, toInsert) ;	
}

void Solve(int N) 
{
	srand( time(0) ) ;
	
	arr.resize(N) ; iota(all(arr) , 0 ) ;
	random_shuffle( all(arr) ) ;

	sub.resize(N) ;
	vis.resize(N) ;
	foundPlace.resize(N) ;
	adj.resize(N, vector<int>() ) ;

	adj[ arr[0] ].push_back( arr[1] ) ;
	adj[ arr[1] ].push_back( arr[0] ) ;

	foundPlace[ arr[0] ] = foundPlace[ arr[1] ] = true ;	

	for(int i = 2 ; i < N ; i++ ) 
	{
		if(foundPlace[ arr[i] ] ) continue ;

		for(int j = 0 ; j < N ; j++ ) vis[j] = false ;
		decompose( arr[i] , arr[0] ) ;
		foundPlace[ arr[i] ] = true ;

	}

	for(int i = 0 ; i < N ; i++ )
		for(auto e : adj[i] )
			if( i < e ) Bridge(i, e) ; 
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71