이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
#define f first
#define s second
#define REP(n) FOR(O, 1, (n))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
const int MAXN = 200;
int n;
int ddd[MAXN][MAXN];
int dist (int a, int b) {
if (a == b) return 0;
if (ddd[a][b] == 0) {
ddd[a][b] = ddd[b][a] = getDistance(a,b);
}
return ddd[a][b];
}
int hubDistance(int N, int sub) {
n = N;
int x = 0, y = 0;
FOR(i, 1, n-1) if (dist(0, i) > dist(0, x)) x = i;
FOR(i, 1, n-1) if (dist(x, i) > dist(x, y)) y = i;
/// x --- y is a diameter
int ans = 1e9;
FOR(i, 0, n-1) {
if (i == x || i == y) continue;
int d1 = dist(x, i), d2 = dist(y, i);
int d = (d1 + d2 - dist(x,y)) / 2;
int a = d1 - d, b = d2 - d;
if (a == 0 || b == 0) continue;
int cur = max(a,b);
ans = min(cur, ans);
}
return ans;
}
/*
1 1
11
0 17 18 20 17 12 20 16 23 20 11
17 0 23 25 22 17 25 21 28 25 16
18 23 0 12 21 16 24 20 27 24 17
20 25 12 0 23 18 26 22 29 26 19
17 22 21 23 0 9 21 17 26 23 16
12 17 16 18 9 0 16 12 21 18 11
20 25 24 26 21 16 0 10 29 26 19
16 21 20 22 17 12 10 0 25 22 15
23 28 27 29 26 21 29 25 0 21 22
20 25 24 26 23 18 26 22 21 0 19
11 16 17 19 16 11 19 15 22 19 0
ans: 16
*/
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
32 | int hubDistance(int N, int sub) {
| ~~~~^~~
# | 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... |