제출 #384338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384338		amoo_safar	Meetings (JOI19_meetings)	C++17	29 / 100	1994 ms	1024 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);
	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: 0 / 71