Submission #344245

#	Time	Username	Problem	Language	Result	Execution time	Memory
344245		Kerim	Meetings (JOI19_meetings)	C++17	100 / 100	783 ms	1004 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)

using namespace std;
int root;
vector<int>path;
bool cmp(int x,int y){
	return (Query(root,x,y)==x);
}
void print(int x,int y){
	if(x>y)swap(x,y);
	Bridge(x,y);	
}
void f(vector<int>v){
	int sz=int(v.size());
	if(sz<2)
		return;
	if(sz==2){
		print(v[0],v[1]);
		return;	
	}
	path.clear();
	int a=rand()%sz,b=rand()%sz;
	while(a==b)b=rand()%sz;
	a=v[a];b=v[b];root=a;
	map<int,vector<int> >pm;
	tr(it,v)
		if(*it!=a && *it!=b){
			int c=Query(a,b,*it);
			if(!pm.count(c) && c!=a && c!=b)
				path.push_back(c);
			pm[c].push_back(*it);	
		}
	pm[a].push_back(a);pm[b].push_back(b);
	if(path.empty())
		print(a,b);
	else{
		sort(path.begin(),path.end(),cmp);
		print(a,path[0]);
		for(int i=0;i<int(path.size())-1;i++)
			print(path[i],path[i+1]);
		print(path.back(),b);
	}
	tr(it,pm)f(it->second);
}
void Solve(int N){
	srand((unsigned)time(NULL));
	vector<int>v;
	for(int i=0;i<N;i++)
		v.push_back(i);
	f(v);
}

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