Submission #378272

#	Time	Username	Problem	Language	Result	Execution time	Memory
378272		pit4h	Meetings (JOI19_meetings)	C++14	100 / 100	802 ms	2076 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int RAND(int l, int r, mt19937& rng) {
	return uniform_int_distribution<int>(l, r)(rng);	
}
void solve(vector<int>& v, mt19937& rng) {
	if((int)v.size()<=1) return;
	if((int)v.size()==2) {
		//cerr<<"bridge: "<<v[0]<<' '<<v[1]<<'\n';
		Bridge(min(v[0], v[1]), max(v[0], v[1]));
		return;
	}
	int sz = v.size();
	int v1 = RAND(0, sz-1, rng), v2 = RAND(0, sz-2, rng);
	if(v2>=v1) v2++;

	//cerr<<"solve [";
	/*for(int i=0; i<sz; ++i) {
		cerr<<v[i];
		if(i<sz-1) cerr<<' ';
		else cerr<<"] ";
	}
	cerr<<v[v1]<<' '<<v[v2]<<"  "<<n<<'\n';
	*/
	vector<vector<int>> vec(n);
	vec[v[v1]].push_back(v[v1]);
	vec[v[v2]].push_back(v[v2]);
	vector<int> path = {v[v1], v[v2]};
	for(int i=0; i<sz; ++i) {
		if(i == v1 || i==v2) continue;
		int u = Query(v[v1], v[v2], v[i]);
		//cerr<<v[i]<<": "<<u<<'\n';
		if(u == v[i]) {
			path.push_back(v[i]);
		}
		vec[u].push_back(v[i]);
	}
	if((int)path.size() == 3) {
		//cerr<<"Bridge: "<<v[0]<<' '<<path[2]<<'\n';
		//cerr<<"Bridge: "<<v[1]<<' '<<path[2]<<'\n';
		Bridge(min(v[v1], path[2]), max(v[v1], path[2]));	
		Bridge(min(v[v2], path[2]), max(v[v2], path[2]));
	}
	else {
		solve(path, rng);
	}
	for(int i=0; i<n; ++i) {
		//cerr<<' '<<i<<" - "<<vec[i].size()<<'\n';
		solve(vec[i], rng);	
	}
}
void Solve(int N) {
	n = N;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<int> v;
	for(int i=0; i<N; ++i) {
		v.push_back(i);
	}
	solve(v, rng);
}

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