Submission #779909

#	Time	Username	Problem	Language	Result	Execution time	Memory
779909		rxlfd314	Meetings (JOI19_meetings)	C++17	100 / 100	1504 ms	1180 KiB

meetings

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

void solve(vector<int> V) {
	if (V.size() < 2) return;
	int a = V[rand()%V.size()], b = V[rand()%V.size()];
	while (b == a) {
		b = V[rand()%V.size()];
	}

	map<int, vector<int>> subtrees;
	vector<int> roots = {a};
	map<int, bool> seen, pushed;
	seen[a] = seen[b] = true;
	for (int i : V) {
		if (seen[i]) continue;
		int c = Query(i, a, b);
		subtrees[c].push_back(i);
		pushed[c] |= c == i;
		if (!seen[c]) {
			roots.push_back(c);
			seen[c] = true;
		}
	}
	roots.push_back(b);
	
	sort(roots.begin(), roots.end(), [&](const int &i, const int &j) {
		return i == a || j == b ? true : i == b || j == a ? false : Query(a, i, j) == i; 
	});
	for (int i = 0; i+1 < roots.size(); i++) {
		Bridge(min(roots[i], roots[i+1]), max(roots[i], roots[i+1]));
	}
	
	//cerr << "Path: " << a << ", " << b << '\n';
	
	for (int i : roots) {
		if (!pushed[i]) {
			subtrees[i].push_back(i);
		}
		//cerr << "Root: " << i << '\n';
		solve(subtrees[i]);
	}
}

void Solve(int N) {
	srand(time(NULL));
	vector<int> v(N);
	iota(v.begin(), v.end(), 0);
	solve(v);
}

Compilation message (stderr)

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

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