Submission #470459

#	Time	Username	Problem	Language	Result	Execution time	Memory
470459		Namnamseo	Meetings (JOI19_meetings)	C++17	100 / 100	839 ms	848 KiB

meetings

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

void bridge(int a, int b) { if (a>b) swap(a, b); Bridge(a, b); }

void work_set(int *v, int n) {
	if (n == 1) return;
	int a = v[0], b = v[1];
	int *par = new int[n]; par[0]=a, par[1]=b;
	for (int i=2; i<n; ++i) par[i]=Query(a, b, v[i]);

	{ int *ps = new int[n]; iota(ps, ps+n, 0);
	sort(ps, ps+n, [&](const int& a, const int& b) { return par[a] < par[b]; });
	for (int i=0, j; i<n; i=j) {
		for (j=i+1; j<n && par[ps[i]]==par[ps[j]]; ++j);
		for (int t=i; t<j; ++t) ps[t] = v[ps[t]];
		work_set(ps+i, j-i);
	}
	delete[] ps; }

	sort(par, par+n);
	n = unique(par, par+n) - par;
	{ int w = 0; for (int i=0; i<n; ++i) {
		if (par[i] == a || par[i] == b) continue;
		if (i != w) par[w] = par[i]; ++w;
	} n = w; }
	if (!n) { bridge(a, b); delete[] par; return; }

	sort(par, par+n, [&](const int& x, const int& y) { return Query(x, y, a) == x; });

	bridge(a, par[0]);
	for (int i=1; i<n; ++i) bridge(par[i-1], par[i]);
	bridge(par[n-1], b);
	delete[] par;
}

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

Compilation message (stderr)

meetings.cpp: In function 'void work_set(int*, int)':
meetings.cpp:29:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   29 |   if (i != w) par[w] = par[i]; ++w;
      |   ^~
meetings.cpp:29:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   29 |   if (i != w) par[w] = par[i]; ++w;
      |                                ^~

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