Submission #828966

#	Time	Username	Problem	Language	Result	Execution time	Memory
828966		MohamedAhmed04	Meetings (JOI19_meetings)	C++14	29 / 100	1861 ms	1212 KiB

meetings

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

using namespace std ;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;

int rand(int l , int r)
{
	return uniform_int_distribution<int>(l , r)(rng) ;
}

const int MAX = 2004 ;

int n ;

vector< pair<int , int> >ans ;

int mark[MAX] ;

void solve(int root , vector<int>v)
{
	if(!v.size())
		return ;
	shuffle(v.begin() , v.end() , rng) ;
	for(auto &node : v)
		mark[node] = 0 ;
	vector< vector<int> >subtrees = {{v.back()}} ;
	v.pop_back() ;
	for(auto &node : v)
	{
		if(mark[node])
			continue ;
		shuffle(subtrees.begin() , subtrees.end() , rng) ;
		mark[node] = 1 ;
		bool flag = false ;
		for(auto &v2 : subtrees)
		{
			int lca = Query(root , node , v2.back()) ;
			if(lca == root)
				continue ;
			flag = true , mark[lca] = 1 ;
			v2.push_back(node) ;
			int sz = v2.size() ;
			if(lca != v2[sz-1])
				swap(v2[sz-1] , v2[sz-2]) ;
			if(lca != v2[sz-1])
				v2.push_back(lca) ;
			break ;
		}
		if(!flag)
			subtrees.push_back({node}) ;
	}
	for(auto &v2 : subtrees)
	{
		int root2 = v2.back() ;
		ans.emplace_back(min(root , root2) , max(root , root2)) ;
		v2.pop_back() ;
		solve(root2 , v2) ;
	}
}

void Solve(int N) 
{
	n = N ;
	int root = rand(0 , n-1) ;
	vector<int>v ;
	for(int i = 0 ; i < n ; ++i)
	{
		if(i != root)
			v.push_back(i) ;
	}
	solve(root , v) ;
	for(auto &p : ans)
		Bridge(p.first , p.second) ;
}

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