Submission #559595

#	Time	Username	Problem	Language	Result	Execution time	Memory
559595		minhcool	Meetings (JOI19_meetings)	C++17	100 / 100	773 ms	992 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
 
using namespace std; 
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e3 + 5, MAXN = 1e7 + 5;
 
const long long oo = 1e9 + 7, mod = 1e9 + 7;

int n;
 
vector<int> vis[N];
 
int sz[N];

//vector<ii> bridge;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	temp = (temp + (r - l + 1)) % (r - l + 1);
	return temp + l;
}

int query(int a, int b, int c){
	//cout << a << " " << b << " " << c << "\n";
	return Query(a - 1, b - 1, c - 1) + 1;
}

void bridge(int a, int b){
	//cout << min(a, b) << " " << max(a, b) << "\n";
	Bridge(min(a, b) - 1, max(a, b) - 1);	
}

bool ck[N];

void solve(vector<int> x){
	for(int i = 1; i <= n; i++) ck[i] = 0;
	if(x.size() <= 1) return;
	if(x.size() == 2){
		bridge(x[0], x[1]);
		return;
	}
	int temp0 = rnd(0, x.size() - 1), temp1 = rnd(0, x.size() - 1), temp2 = rnd(0, x.size() - 1);
	while(temp1 == temp0) temp1 = rnd(0, x.size() - 1);
	while(temp2 == temp0 || temp2 == temp1) temp2 = rnd(0, x.size() - 1);
	int node = query(x[temp0], x[temp1], x[temp2]);
	int node2 = (x[0] == node ? x[1] : x[0]);
	//cout << temp << " " << node << " " << node2 << "\n";
	//assert(node != node2);
	for(auto it : x){
		if(it == node || it == node2) continue;
		int temp = query(node, node2, it);
		if(temp == node){
			ck[it] = 1;
			continue;
		}
		node2 = temp;
	}
	//cout << node << " " << node2 << "\n";
	bridge(node, node2);
	vector<int> x1, x2;
	x1.pb(node), x2.pb(node2);
	for(auto it : x){
		if(it == node || it == node2) continue;
		//int temp = query(node, node2, it);
		//assert(temp == node || temp == node2);
		if(ck[it]) x1.pb(it);
		else x2.pb(it);	
	}
	solve(x1), solve(x2);
}
void Solve(int _n){
	n = _n;
	vector<int> str;
	for(int i = 1; i <= n; i++) str.pb(i);
	solve(str);
}
 
/*
5
0 1
0 2
1 3
1 4
*/

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