Submission #472688

#	Time	Username	Problem	Language	Result	Execution time	Memory
472688		prvocislo	Meetings (JOI19_meetings)	C++17	100 / 100	1107 ms	872 KiB

meetings

#include "meetings.h"
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int x, y;
bool cmp(int a, int b) 
{ 
	if (a == x) return true;
	if (b == x || a == b) return false;
	return Query(x, a, b) == a; 
}
void solve(const vector<int>& v)
{
	if (v.size() == 1) return;
	x = y = v[rand() % v.size()];
	while (x == y) y = v[rand() % v.size()];
	map<int, vector<int> > m;
	m[x].push_back(x);
	m[y].push_back(y);
	vector<int> path = { x, y };
	for (int i : v) if (x != i && y != i)
	{
		int qi = Query(x, y, i);
		if (qi == i) path.push_back(i);
		m[qi].push_back(i);
	}
	sort(path.begin(), path.end(), cmp);
	for (int i = 0; i < path.size() - 1; i++) 
		Bridge(min(path[i], path[i+1]), max(path[i], path[i + 1]));
	for (const pair<int, vector<int> >& i : m) solve(i.second);
}
void Solve(int N)
{
	vector<int> path;
	for (int i = 0; i < N; i++) path.push_back(i);
	solve(path);
}

Compilation message (stderr)

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

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