이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// this isn't mine, I'm just asserting something
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
int v = 0, s, t, r;
int distv[120], dists[120];
bool sameConn(int x1, int x2) {
int x = getDistance(x1, x2);
return (dists[x1] + dists[x2] - x > 2 * r);
}
int hubDistance(int N, int sub) {
int maxv = 0;
for(int i = 0 ; i < N ; i++) {
distv[i] = getDistance(v, i);
maxv = max(maxv, distv[i]);
}
for(int i = 0 ; i < N ; i++)
if(distv[i] == maxv)
s = i;
int dsv = maxv;
maxv = 0;
for(int i = 0 ; i < N ; i++) {
dists[i] = getDistance(s, i);
maxv = max(maxv, dists[i]);
}
int d = maxv;
for(int i = 0 ; i < N ; i++)
if(dists[i] == maxv)
t = i;
int res = 1e9;
vector<int> poss;
for(int i = 0 ; i < N ; i++) {
int a = (dists[i] + dsv - distv[i]) / 2;
int b = dsv - a;
if(max({a, b, d - a}) < res) {
res = max({a, b, d - a});
poss.clear();
poss.push_back(a);
} else if(max({a, b, d - a}) == res)
poss.push_back(a);
//~ cout << i << " " << res << endl;
}
vector<int> B;
for(int i = 0 ; i < N ; i++)
B.push_back((dists[i] + dsv - distv[i]) / 2);
sort(B.begin(), B.end());
int m;
if(B.size() % 2 == 0) {
int m1 = B[B.size() / 2 - 1];
int m2 = B[B.size() / 2];
if(m1 == m2)
m = m1;
else {
if(find(poss.begin(), poss.end(), m1) == poss.end()
&& find(poss.begin(), poss.end(), m2) == poss.end()) {
//~ cout << "aa" << endl;
return -res;
}
return res;
}
} else
m = B[B.size() / 2];
if(find(poss.begin(), poss.end(), m) == poss.end()) {
//~ cout << "aa" << endl;
return -res;
}
r = m;
vector<int> list, bucket;
for(int i = 0 ; i < N ; i++) {
if((dists[i] + dsv - distv[i]) / 2 == m) {
if(list.empty() || !sameConn(i, list.back())) {
list.push_back(i);
if(!bucket.empty()) {
list.push_back(bucket.back());
bucket.pop_back();
}
} else
bucket.push_back(i);
}
}
int T = list.back();
int cnt = 0;
while(!list.empty()) {
if(sameConn(list.back(), T)) {
cnt++;
if(list.size() > 1) {
list.pop_back();
list.pop_back();
} else {
list.pop_back();
}
} else {
list.pop_back();
}
}
cnt += bucket.size();
if(cnt <= N / 2) {
//~ cout << "c" << endl;
return res;
}
//~ cout << "ab" << endl;
return -res;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:119:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
cnt += bucket.size();
^
towns.cpp:20: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... |