Submission #116431

#	Time	Username	Problem	Language	Result	Execution time	Memory
116431		Mamnoon_Siam	Meetings (JOI19_meetings)	C++17	100 / 100	965 ms	3768 KiB

meetings

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

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

const int maxn = 2e3 + 5;
using ii = pair<int, int>;

int n;
set<ii> ans;
map<int, map<int, map<int, int>>> mem;

int ask(int u, int v, int w) {
	{
		int mn = min({u, v, w});
		int mx = max({u, v, w});
		int md = u + v + w - mn - mx;
		u = mn, v = md, w = mx;
	}
	if(u == v or v == w) return v;
	if(mem[u][v].find(w) == mem[u][v].end()) return mem[u][v][w] = Query(u, v, w);
	else return mem[u][v][w];
}

void add_edge(int u, int v) {
	if(u > v) swap(u, v);
	// cout << "addded = " << u << ' ' << v << endl;
	ans.insert(ii(u, v));
}

void solve(vector<int> &s) {
	if(s.size() < 2) return;
	if(s.size() == 2) {
		add_edge(s[0], s[1]);
		return;
	}
	shuffle(s.begin(), s.end(), rng);
	set<int> path_nodes;
	map<int, int> mp;
	int p = s[0], q = s[1];
	for(int u : s) {
		mp[u] = ask(p, q, u);
		path_nodes.insert(mp[u]);
	}
	path_nodes.erase(p);
	path_nodes.erase(q);
	vector<int> path(path_nodes.begin(), path_nodes.end());
	shuffle(path.begin(), path.end(), rng);
	sort(path.begin(), path.end(), [&](int u, int v){ return ask(p, u, v) == u; });
	for(int i = 1; i < path.size(); i++) {
		add_edge(path[i - 1], path[i]);
	}
	if(path.size()) {
		add_edge(path[0], p);
		add_edge(path.back(), q);
	} else add_edge(p, q);
	map<int, vector<int>> to;
	for(auto i : mp) {
		to[i.second].emplace_back(i.first);
	}
	for(auto i : to) {
		solve(i.second);
	}
}

void Solve(int N) {
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	solve(v);
	for(ii i : ans) Bridge(i.first, i.second);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>&)':
meetings.cpp:52: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