Submission #929500

#	Time	Username	Problem	Language	Result	Execution time	Memory
929500		horiseun	Meetings (JOI19_meetings)	C++17	100 / 100	1004 ms	1016 KiB

meetings

#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <random>
#include <cassert>
#include <numeric>
#include <algorithm>
#include "meetings.h"
using namespace std;

#define f first
#define s second

vector<pair<int, int>> ans;
mt19937 rd(4315143);

int query(int x, int y, int z) {
	if (x == y || x == z) return x;
	if (y == z) return y;
	return Query(x, y, z);
}

void solve(vector<int> v) {
	if (v.size() <= 1) return;
	shuffle(v.begin(), v.end(), rd);
	int x = v[0], y = v[1];
	for (int i = 2, ret; i < v.size(); i++) {
		ret = query(x, y, v[i]);
		if (ret == x) {
			x = v[i];
		} else if (ret == y) {
			y = v[i];
		}
	}
	map<int, vector<int>> groups;
	for (int i = 0, ret; i < v.size(); i++) {
		if (v[i] == x || v[i] == y) continue;
		ret = query(x, y, v[i]);
		groups[ret].push_back(v[i]);
	}
	vector<int> curr;
	curr.push_back(x);
	curr.push_back(y);
	for (pair<int, vector<int>> g : groups) {
		curr.push_back(g.f);
	}
	sort(curr.begin(), curr.end(), [&] (int a, int b) {
		int ret = query(x, a, b);
		return ret == a;
	});
	for (int i = 0; i < curr.size() - 1; i++) {
		ans.push_back({curr[i], curr[i + 1]});
	}
	for (pair<int, vector<int>> g : groups) {
		solve(g.s);
	}
}

void Solve(int N) {
	vector<int> tmp(N);
	iota(tmp.begin(), tmp.end(), 0);
	solve(tmp);
	for (auto [x, y] : ans) {
		assert(x != y);
		if (y < x) swap(x, y);
		Bridge(x, y);
	}
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:28:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 2, ret; i < v.size(); i++) {
      |                       ~~^~~~~~~~~~
meetings.cpp:37:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i = 0, ret; i < v.size(); i++) {
      |                       ~~^~~~~~~~~~
meetings.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < curr.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

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