이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool samecomp(vector<int> &lngv, int v1, int v2, int r)
{
if (lngv[v1] + lngv[2] - 2*r > getDistance(v1, v2)) return true;
return false;
}
int hubDistance(int n, int sub) {
int mmax = -1;
int diabeg = -1;
for (int i = 1; i < n; i++)
{
int q = getDistance(0, i);
if (q > mmax)
{
mmax = q;
diabeg = i;
}
}
vector<int> fbeg(n);
int diaend = -1;
mmax = -1;
for (int i = 0; i < n; i++)
{
if (i == diabeg) continue;
fbeg[i] = getDistance(diabeg, i);
if (fbeg[i] > mmax)
{
mmax = fbeg[i];
diaend = i;
}
}
vector<int> fend(n);
fend[diabeg] = fbeg[diaend];
for (int i = 0; i < n; i++)
{
if (i == diabeg || i == diaend) continue;
fend[i] = getDistance(diaend, i);
}
int r = 100000000;
int dia = fbeg[diaend];
for (int i = 0; i < n; i++)
{
int diff = abs(fbeg[i] - fend[i]);
r = min(r, (dia + diff)/2);
}
for (int i = 0; i < n; i++)
{
if (r == (dia + abs(fbeg[i] - fend[i]))/2)
{
if (fbeg[i] - fend[i] < 0)
{
swap(fbeg, fend);
swap(diabeg, diaend);
}
break;
}
}
vector<int> ext;
int cntl = 0, cntr = 0;
for (int i = 0; i < n; i++)
{
if (r == (dia + fbeg[i] - fend[i])/2)
{
ext.push_back(i);
}
else
{
if ((dia + fbeg[i] - fend[i])/2 < r) cntl++;
else cntr++;
}
}
if (cntl > (n / 2) || cntr > (n/2)) return -r;
vector<int> st;
for (int j : ext)
{
if (st.empty())
{
st.push_back(j);
}
else
{
if (samecomp(fbeg, j, st.back(), r)) st.push_back(j);
else st.pop_back();
}
}
if (st.empty()) return r;
int cnt = 0;
for (int i : ext)
{
if (i == st.back()) continue;
else cnt += (samecomp(fbeg, i, st.back(), r));
}
return r;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:14:28: warning: unused parameter 'sub' [-Wunused-parameter]
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... |