# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
434589 | Tangent | 도시들 (IOI15_towns) | C++17 | 1095 ms | 816 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()
map<pii, int> memo;
int dist(int u, int v) {
if (!memo[{u, v}]) {
memo[{u, v}] = memo[{v, u}] = getDistance(u, v);
}
return memo[{u, v}];
}
int hubDistance(int n, int sub) {
int res = 1000000000;
// vector<map<int, int>> hubds(n);
// vvii hubs;
rep(i, n - 1) {
ffor(j, i + 1, n) {
map<int, int> xs;
rep(k, n) {
if (k == i || k == j) {
continue;
}
int a = dist(i, j), b = dist(j, k), c = dist(i, k);
int x = (a + c - b) / 2, y = (a + b - c) / 2, z = (b + c - a) / 2;
// int hub;
// if (hubds[i].find(x) != hubds[i].end()) {
// hub = hubds[i][x];
// } else if (hubds[j].find(y) != hubds[j].end()) {
// hub = hubds[j][y];
// } else if (hubds[k].find(z) != hubds[k].end()) {
// hub = hubds[k][z];
// } else {
// hub = hubs.size();
// hubs.emplace_back(vii(n));
// }
// hubds[i][x] = hubds[j][y] = hubds[k][z] = hub;
// hubs[hub][i] = x;
// hubs[hub][j] = y;
// hubs[hub][k] = z;
xs[x] = max(xs[x], max(x, max(y, z)));
}
forin(p, xs) {
int curr = p.second;
forin(p2, xs) {
if (p != p2) {
curr = max(curr, abs(p2.first - p.first) + p2.second);
}
}
res = min(res, curr);
}
}
}
// forin(hub, hubs) {
// res = min(res, *max_element(all(hub)));
// }
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |