Submission #829318

#	Time	Username	Problem	Language	Result	Execution time	Memory
829318		MohamedAhmed04	Meetings (JOI19_meetings)	C++14	100 / 100	664 ms	860 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 ;

vector<int>subtree[MAX] ;

int curroot ;

bool cmp(int &a , int &b)
{
	return (Query(curroot , a , b) == a) ;
}

void solve(int root , vector<int>v)
{
	if(!v.size())
		return ;
	curroot = root ;
	shuffle(v.begin() , v.end() , rng) ;
	subtree[root].clear() ;
	for(auto &node : v)
		subtree[node].clear() ;
	int x = v.back() ;
	v.pop_back() ;
	vector<int>path = {x} ;
	for(auto &node : v)
	{
		int lca = Query(root , x , node) ;
		if(lca != node)
			subtree[lca].push_back(node) ;
		if(lca != root)
			path.push_back(lca) ;
	}
	sort(path.begin() , path.end()) ;
	path.erase(unique(path.begin() , path.end()) , path.end()) ;
	sort(path.begin() , path.end() , cmp) ;
	ans.emplace_back(root , path[0]) ;
	for(int i = 0 ; i+1 < path.size() ; ++i)
		ans.emplace_back(path[i] , path[i+1]) ;
	solve(root , subtree[root]) ;
	for(auto &node : path)
		solve(node , subtree[node]) ;
}

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(min(p.first , p.second) , max(p.first , p.second)) ;
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(int, std::vector<int>)':
meetings.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0 ; i+1 < path.size() ; ++i)
      |                  ~~~~^~~~~~~~~~~~~

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