Submission #278632

#	Time	Username	Problem	Language	Result	Execution time	Memory
278632		rqi	Meetings (JOI19_meetings)	C++14	100 / 100	966 ms	1144 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define ins insert
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)

const int MOD = 1000000007;
const int mx = 2005;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

int N;
// set<int> below[mx];
// bool leaved[mx];

void bridge(int a, int b){
	assert(a != b);
	if(a > b) swap(a, b);
	assert(0 <= a && b <= N-1);
	//cout << a << " " << b << "\n";
	Bridge(a, b);
}

int curR;

bool cmp(const int &a, const int &b){
	int A = a;
	int B = b;
	if(Query(A, B, curR) == b) return 1;
	return 0;
}

vi cSort(set<int> x){
	vi v;
	for(auto u: x){
		v.pb(u);
	}
	sort(all(v), cmp);
	return v;
}

void search(int R, vi nodes){
	// cout << "search: " << R << ", ";
	// for(auto u: nodes){
	// 	cout << u << " ";
	// }
	// cout << "\n";
	if(sz(nodes) == 0) return;
	if(sz(nodes) == 1){
		bridge(nodes[0], R);
		return;
	}
	int cur = nodes[rng() % sz(nodes)];
	//cout << "cur: " << cur << "\n";
	map<int, vi> m;
	set<int> path;
	path.ins(R);
	path.ins(cur);
	for(auto u: nodes){
		if(u == cur) continue;
		int a = Query(R, cur, u);
		path.ins(a);
		if(a != u) m[a].pb(u);
	}
	curR = R;
	// cout << "path: ";
	// for(auto u: path) cout << u << " ";
	// cout << "\n";
	if(path.count(cur)) path.erase(cur);
	if(path.count(R)) path.erase(R);
	vi v = cSort(path); //lowest to highest in tree
	vi newv;
	newv.pb(cur);
	for(auto u: v) newv.pb(u);
	newv.pb(R);
	swap(v, newv);
	// cout << "v: ";
	// for(auto u: v) cout << u << " ";
	// cout << "\n";
	for(int i = 0; i+1 < sz(v); i++){
		bridge(v[i], v[i+1]);
	}
	for(auto u: m){
		search(u.f, u.s);
	}
}

void Solve(int _N) {
	N = _N;
	// for(int i = 1; i < N; i++){
	// 	for(int j = i+1; j < N; j++){
	// 		int a = Query(0, i, j);
	// 		if(a != i) below[a].ins(i);
	// 		if(a != j) below[a].ins(j);
	// 	}
	// }
	// for(int i = 0; i < N-1; i++){
	// 	//cout << "Phase " << i << "\n";
	// 	int leaf;
	// 	for(int j = 1; j < N; j++){
	// 		if(leaved[j]) continue;
	// 		if(sz(below[j]) == 0){
	// 			leaf = j;
	// 			break;
	// 		}
	// 	}
	// 	//cout << leaf << "\n";
	// 	leaved[leaf] = 1;
	// 	pi cur = mp(MOD, -1);
	// 	for(int j = 0; j < N; j++){
	// 		if(leaved[j]) continue;
	// 		if(below[j].count(leaf)) cur = min(cur, mp(sz(below[j]), j));
	// 	}
	// 	if(cur.s == -1) cur.s = 0;
	// 	for(int j = 0; j < N; j++){
	// 		if(below[j].count(leaf)) below[j].erase(leaf);
	// 	}
	// 	Bridge(min(leaf, cur.s), max(leaf, cur.s));
	// }
	vi init;
	for(int i = 1; i < N; i++){
		init.pb(i);
	}
	search(0, init);
}

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