이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#include "towns.h"
int getDistance(int a, int b);
const int N = 110;
int dist_0[N], dist_u[N], x[N], y[N], color[N];
int hubDistance(int n, int subtask) {
for (int i = 1; i < n; ++i) {
dist_0[i] = getDistance(0, i);
}
int u = max_element(dist_0, dist_0 + n) - dist_0;
dist_u[0] = dist_0[u];
for (int i = 1; i < n; ++i) {
if (i != u) {
dist_u[i] = getDistance(u, i);
}
}
int ans = n;
map<int, vector<int>> groups;
int diameter = *max_element(dist_u, dist_u + n);
for (int i = 0; i < n; ++i) {
y[i] = (dist_u[i] + dist_0[i] - dist_0[u]) / 2;
x[i] = dist_u[i] - x[i];
ans = min(ans, max(x[i], diameter - x[i]));
groups[x[i]].push_back(i);
}
int left = 0, right = n;
for (auto &[dist, nodes] : groups) {
right -= nodes.size();
if (max(dist, diameter - dist) == ans) {
if (left <= n / 2 && right <= n / 2) {
int i = -1, balance = 0;
for (auto j : nodes) {
if (balance == 0) {
i = j;
}
if (i == j || getDistance(i, j) < y[i] + y[j]) {
color[j] = i, ++balance;
} else {
color[j] = j, --balance;
}
}
int k = -1, size = 0;
for (auto j : nodes) {
if (color[j] == j && getDistance(i, j) < y[i] + y[j]) {
k = j;
}
size += color[j] == k;
}
return size <= n / 2 ? ans : -ans;
}
}
left += nodes.size();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:17:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
17 | int u = max_element(dist_0, dist_0 + n) - dist_0;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:38:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
38 | right -= nodes.size();
| ^
towns.cpp:64:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
64 | left += nodes.size();
| ^
towns.cpp:12:28: warning: unused parameter 'subtask' [-Wunused-parameter]
12 | int hubDistance(int n, int subtask) {
| ~~~~^~~~~~~
# | 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... |