| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 242642 | ZwariowanyMarcin | Meetings (JOI19_meetings) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 2100;
/*
int Query(int x, int y, int z) {
printf ("ask %d %d %d\n", x, y, z);
int d;
cin >> d;
return d;
}
void Bridge(int x, int y) {
printf ("tree %d %d\n", x, y);
}*/
vector <int> g[N];
void rek(vector <int> x, int root) {
if (ss(x) == 1) return;
int y = x[rand() % ss(x)];
while (y == root)
y = x[rand() % ss(x)];
for (auto it : x)
g[it].clear();
vector <int> path;
for (auto it : x) {
if (it == y || it == root) continue;
int z = Query(root, y, it);
if (it == z) path.pb(it);
g[z].pb(it);
}
g[root].pb(root);
g[y].pb(y);
sort(all(path), [&](int a, int b) {
int c = Query(root, a, b);
if (c == a) return 1;
else return 0;
});
// 1.
int First = (path.empty() ? y : path[0]);
Bridge(First, root);
rep(i, 0, ss(path) - 1)
Bridge(path[i], (i + 1 < ss(path) ? path[i + 1] : y));
for (auto it : x)
if (!g[it].empty())
rek(g[it], it);
}
void Solve(int n) {
vector <int> v(n);
iota(all(v), 0);
int root = rand() % n;
rek(v, root);
}
int main() {
srand(2137);
Solve(3);
return 0;
}