Submission #429107

#	Time	Username	Problem	Language	Result	Execution time	Memory
429107		koioi.org-koosaga	Meetings (JOI19_meetings)	C++17	100 / 100	1931 ms	824 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;

mt19937 rng(0x14004);
int randint(int lb, int ub){ return uniform_int_distribution<int>(lb, ub)(rng); }

void bridge(int x, int y){ Bridge(min(x, y), max(x, y)); }

void dfs(vector<int> v){
	if(v.size() == 1) return;
	if(v.size() == 2){
		bridge(v[0], v[1]);
		return;
	}
	map<int, int> mp;
    shuffle(v.begin(), v.end(), rng);
	for(int i=2; i<v.size(); i++){
		int q = Query(v[0], v[1], v[i]);
		mp[q]++;
	}
	pi ret(-1, -1);
	for(auto &i : mp){
		ret = max(ret, pi(i.second, i.first));
	}
	int c = ret.second;
	vector<vector<int>> anclist;
	for(auto &i : v){
		if(i == c) continue;
		bool found = 0;
		for(auto &j : anclist){
			if(find(j.begin(), j.end(), i) != j.end()){
				found = 1;
				break;
			}
		}
		if(found) continue;
		for(auto &j : anclist){
			int x = Query(i, j[0], c);
			if(x == c) continue;
			j.push_back(i);
			if(find(j.begin(), j.end(), x) == j.end()) j.push_back(x);
			swap(j[0], *find(j.begin(), j.end(), x));
			found = 1;
			break;
		}
		if(!found){
			anclist.push_back({i});
		}
	}
	for(auto &i : anclist){
		bridge(c, i[0]);
		dfs(i);
	}
}

void Solve(int N) {
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	dfs(v);
}

Compilation message (stderr)

meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=2; i<v.size(); i++){
      |               ~^~~~~~~~~

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