| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 136771 | E869120 | Meetings (JOI19_meetings) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <vector>
#include <ctime>
using namespace std;
vector<pair<int, int>> T;
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 = Query(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 = Query(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 = Query(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 = Query(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;
}