Submission #226609

#	Time	Username	Problem	Language	Result	Execution time	Memory
226609		Bruteforceman	Meetings (JOI19_meetings)	C++17	100 / 100	1014 ms	1144 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
mt19937 rng;
vector <int> can[2222];

int piv;
int cmp(int x, int y) {
	return Query(piv, x, y) == x;
}
void solver(vector <int> v) {
	if(v.size() <= 1) return ;
	shuffle(v.begin(), v.end(), rng);
	int p = v[0];
	int q = v[1];
	vector <int> path;
	for(int i : v) {
		can[i].clear();
	}
	can[p].emplace_back(p);
	can[q].emplace_back(q);
	for(int i = 2; i < v.size(); i++) {
		int x = Query(p, q, v[i]);
		can[x].emplace_back(v[i]);
		if(v[i] == x) {
			path.emplace_back(x);
		}
	}
	piv = p;
	sort(path.begin(), path.end(), cmp);
	path.insert(path.begin(), p);
	path.push_back(q);
	for(int i = 1; i < path.size(); i++) {
		int u = path[i - 1];
		int v = path[i];
		if(u > v) swap(u, v);
		Bridge(u, v);
		// cout << path[i - 1] << ' ' << path[i] << endl;
	}
	for(int i : path) {
		solver(can[i]);
	}
}

void Solve(int N) {
  rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
  vector <int> v;
  for(int i = 0; i < N; i++) {
  	v.emplace_back(i);
  }
  solver(v);
}

Compilation message (stderr)

meetings.cpp: In function 'void solver(std::vector<int>)':
meetings.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < v.size(); i++) {
                 ~~^~~~~~~~~~
meetings.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < path.size(); i++) {
                 ~~^~~~~~~~~~~~~

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