제출 #136775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
136775		E869120	Meetings (JOI19_meetings)	C++14	29 / 100	2608 ms	3972 KiB

meetings

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

vector<pair<int, int>> T;
map<tuple<int, int, int>, int> Map;

int Ask(int a1, int a2, int a3) {
	int v[3] = { a1, a2, a3 }; sort(v, v + 3);
	a1 = v[0]; a2 = v[1]; a3 = v[2];
	if (Map[make_tuple(a1, a2, a3)] >= 1) return Map[make_tuple(a1, a2, a3)];
	
	int x = Query(a1, a2, a3);
	Map[make_tuple(a1, a2, a3)] = x;
	return x;
}

vector<int> random_shuffle(vector<int> I) {
	for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
	return I;
}

void dfs(vector<int> vec) {
	// サイズが 1, 2, 3 のときに場合分け
	if (vec.size() == 1) return;
	if (vec.size() == 2) {
		T.push_back(make_pair(vec[0], vec[1]));
		return;
	}
	if (vec.size() == 3) {
		int S = Ask(vec[0], vec[1], vec[2]);
		if (vec[0] != S) T.push_back(make_pair(vec[0], S));
		if (vec[1] != S) T.push_back(make_pair(vec[1], S));
		if (vec[2] != S) T.push_back(make_pair(vec[2], S));
		return;
	}

	vec = random_shuffle(vec);
	while (true) {
		// 乱択アルゴリズムで重心を見つける
		int v = vec[rand() % vec.size()], cnt = 0;
		for (int t = 0; t < 8; t++) {
			int v1 = v, v2 = v;
			while (v1 == v2 || v1 == v || v2 == v) {
				v1 = vec[rand() % vec.size()];
				v2 = vec[rand() % vec.size()];
			}
			int S = Ask(v, v1, v2);
			if (S == v) cnt++;
		}
		
		if (cnt <= 2) continue;

		// 連結成分ごとに分ける
		vector<int>col(vec.size(), -1); int cnts = 0;
		for (int t = 0; t < vec.size(); t++) {
			if (col[t] >= 0 || vec[t] == v) continue;
			cnts++; col[t] = cnts;
			for (int j = 0; j < vec.size(); j++) {
				if (col[j] >= 0 || vec[j] == v) continue;
				int S = Ask(v, vec[t], vec[j]);
				if (S != v) { col[j] = cnts; }
			}
		}

		for (int t = 1; t <= cnts; t++) {
			vector<int>E;
			for (int j = 0; j < vec.size(); j++) {
				if (col[j] == t) E.push_back(vec[j]);
			}
			int cur = E[0];
			for (int j = 1; j < E.size(); j++) {
				int F = Ask(v, cur, E[j]);
				if (F == E[j]) cur = E[j];
			}
			T.push_back(make_pair(v, cur));
			dfs(E);
		}
		break;
	}
}

void Solve(int N) {
	srand((unsigned)time(NULL));
	vector<int> vec;
	for (int i = 0; i < N; i++) vec.push_back(i);
	dfs(vec);

	for (int i = 0; i < T.size(); i++) {
		if (T[i].first > T[i].second) swap(T[i].first, T[i].second);
		Bridge(T[i].first, T[i].second);
	}
	return;
}

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In function 'std::vector<int> random_shuffle(std::vector<int>)':
meetings.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
                  ~~^~~~~~~~~~
meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int t = 0; t < vec.size(); t++) {
                   ~~^~~~~~~~~~~~
meetings.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < vec.size(); j++) {
                    ~~^~~~~~~~~~~~
meetings.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < vec.size(); j++) {
                    ~~^~~~~~~~~~~~
meetings.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 1; j < E.size(); j++) {
                    ~~^~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size(); i++) {
                  ~~^~~~~~~~~~

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