Submission #123914

#	Time	Username	Problem	Language	Result	Execution time	Memory
123914		onjo0127	Meetings (JOI19_meetings)	C++14	100 / 100	1615 ms	16692 KiB

meetings

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

int query(int u, int v, int w) {
	if(u == v) return u;
	if(v == w) return v;
	if(w == u) return w;
	return Query(u, v, w);
}

void bridge(int u, int v) {
	if(u > v) swap(u, v);
	Bridge(u, v);
}

int D[2009][2009];

void go(vector<int> &S, int u) {
	int N = S.size();
	if(N == 1) return;
	if(N == 2) {
		bridge(S[0], S[1]);
		return;
	}
	int tmp;
	while(1) {
		tmp = S[rand() % N];
		if(tmp != u) break;
	}
	int v = tmp;

	vector<bool> chk(N, 0);
	map<int, vector<int> > mp;
	vector<int> T, U, V;
	for(auto& it: S) {
		int Q = query(u, v, it);
		mp[Q].push_back(it);
		if(Q != u && Q != v) T.push_back(Q);
	}

	if(T.size()) {
		sort(T.begin(), T.end(), [&](int X, int Y) {
			if(D[X][Y] != -1) return D[X][Y];
			int f = (query(u, X, Y) == X);
			D[X][Y] = f; D[Y][X] = !f;
			return f;
		});
		T.resize(unique(T.begin(), T.end()) - T.begin());
		for(int i=1; i<T.size(); i++) bridge(T[i-1], T[i]);
		bridge(u, T[0]); bridge(T.back(), v);
	}
	else bridge(u, v);

	for(auto& it: mp) go(it.second, it.first);
}

void Solve(int N) {
	srand(190702);
	vector<int> S;
	for(int i=0; i<N; i++) S.push_back(i);
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(i == j) D[i][j] = 0;
			else D[i][j] = -1;
		}
	}
	go(S, 0);
}

Compilation message (stderr)

meetings.cpp: In function 'void go(std::vector<int>&, int)':
meetings.cpp:50:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<T.size(); i++) bridge(T[i-1], T[i]);
                ~^~~~~~~~~

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