Submission #344241

#	Time	Username	Problem	Language	Result	Execution time	Memory
344241		Kerim	Meetings (JOI19_meetings)	C++17	100 / 100	658 ms	1092 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;
bool cmp(int x,int y){
	return (Query(root,x,y)==x);
}
void print(int x,int y){
	if(x>y)swap(x,y);
	//printf("%d %d\n",x,y);
	Bridge(x,y);	
}
void f(vector<int>v){
	int sz=int(v.size());
	if(sz<2)
		return;
	/*printf("v= ");
	tr(it,v)
		printf("%d ",*it);
	puts("");*/
	if(sz==2){
		print(v[0],v[1]);
		return;	
	}
	int a=rand()%sz,b=rand()%sz;while(a==b)b=rand()%sz;
	//int a=0,b=1;
	a=v[a];b=v[b];root=a;
	//printf("a=%d\n",a);
	//printf("b=%d\n",b);
	map<int,vector<int> >pm;
	vector<int>tmp;
	tr(it,v)
		if(*it!=a && *it!=b){
			int c=Query(a,b,*it);
			//printf("c = %d %d,%d,%d\n",c,a,b,*it);
			if(!pm.count(c) && c!=a && c!=b)
				tmp.push_back(c);
			pm[c].push_back(*it);	
		}
	pm[a].push_back(a);pm[b].push_back(b);
	if(tmp.empty())
		print(a,b);
	else{
		sort(tmp.begin(),tmp.end(),cmp);
		/*printf("tmp=");
		tr(it,tmp)
			printf("%d ",*it);
		puts("");
		printf("So?");*/
		print(a,tmp[0]);
		for(int i=0;i<int(tmp.size())-1;i++)
			print(tmp[i],tmp[i+1]);
		print(tmp.back(),b);
	}
	tr(it,pm){
		//printf("GO %d\n",it->first);
		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