Submission #409856

#	Time	Username	Problem	Language	Result	Execution time	Memory
409856		amoo_safar	Meetings (JOI19_meetings)	C++17	100 / 100	841 ms	924 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

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

int rand(int bd){
	int res = bd;
	while(res == bd){
		res = uniform_int_distribution<int>(0, bd)(Amoo);
	}
	return res;
}
void bridge(int u, int v){
	if(u > v) swap(u, v);
	Bridge(u, v);
}

void solve(vector<int> V){
	// cerr << "! "; 
	// for(auto al : V) cerr << al << ' ';
	// cerr << '\n';
	int n = V.size();
	if(n == 1) return ;
	if(n == 2){
		bridge(V[0], V[1]);
		return ;
	}
	int a = rand(n);
	int b = a;
	while(b == a) b = rand(n);
	a = V[a];
	b = V[b];
	map<int, vector<int> > mp;
	mp[a].pb(a);
	mp[b].pb(b);
	
	for(auto x : V){
		if(x == a || x == b) continue;
		mp[Query(a, b, x)].pb(x);
	}
	vector<int> P;
	for(auto [x, vec] : mp){
		if(x != a)
			P.pb(x);
		solve(vec);
	}
	sort(P.begin(), P.end(), [&](int u, int v){
		return Query(a, u, v) == u;
	});
	bridge(a, P[0]);
	for(int i = 0; i + 1 < (int) P.size(); i++)
		bridge(P[i], P[i + 1]);
	// int c = a;
	// while(c == a || c == b) c = rand(n);
	// int rt = Query(V[a], V[b], V[c]);
	// vector<int> Y;
	// for(auto x : V) if(x != rt) Y.pb(x);
	// vector<vector<int>> M;
	// vector<int> mx;
	// M.pb( {Y[0]} ); mx.pb(Y[0]);
	// int res;
	// for(int i = 1; i < (int) Y.size(); i++){
	// 	int fl = 1;
	// 	for(int j = 0; j < (int) mx.size(); j++){
	// 		res = Query(rt, mx[j], Y[i]);
	// 		if(res != rt){

	// 			M[j].pb(Y[i]);
	// 			if(res == Y[i])
	// 				mx[j] = Y[i];
	// 			fl = 0;
	// 			break;
	// 		}
	// 	}
	// 	if(fl){
	// 		M.pb({Y[i]});
	// 		mx.pb(Y[i]);
	// 	}
	// }
	// for(auto u : mx)
	// 	bridge(rt, u);
	// for(auto I : M) solve(I);

}

void Solve(int N) {
	vector<int> A(N);
	iota(A.begin(), A.end(), 0);
	solve(A);
}

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