Submission #1029332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029332		Blagoj	Meetings (JOI19_meetings)	C++17	100 / 100	683 ms	16004 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 2e4 + 100;

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


vector<int> C[mxn];

void merge(int a, int b) {
	Bridge(min(a, b), max(a, b));
}

void solve(vector<int> v) {
	int n = v.size();
	if (n < 2) return;
	shuffle(all(v), rng);
	int x = v[0], y = v[1];
	vector<int> between;
	C[x].push_back(x);
	C[y].push_back(y);
	for (int i = 2; i < n; i++) {
		int val = Query(x, y, v[i]);
		if (val == v[i]) between.push_back(v[i]);
		C[val].push_back(v[i]);
	}
	sort(all(between), [&] (int a, int b) {
		return Query(x, a, b) == a;
	});
	between.insert(between.begin(), x);
	between.push_back(y);
	for (int i = 1; i < between.size(); i++) merge(between[i - 1], between[i]);
	vector<vector<int>> toDo;
	for (auto el : C) toDo.push_back(el);
	for (auto el : between) C[el].clear();
	for (auto el : toDo) solve(el); 
}

void Solve(int N) {
	vector<int> v;
	for (int i = 0; i < N; i++) v.push_back(i);
	solve(v); 
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 1; i < between.size(); i++) merge(between[i - 1], between[i]);
      |                  ~~^~~~~~~~~~~~~~~~

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