# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
795393 | jasmin | 도시들 (IOI15_towns) | C++17 | 16 ms | 884 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int hubDistance(int n, int sub) {
//find diameter
vector<int> dist0(n);
int a=1;
for(int i=1; i<n; i++){
dist0[i] = getDistance(0, i);
if(dist0[i]>dist0[a]){
a=i;
}
}
int b=0;
vector<int> dista(n);
dista[0] = dist0[a];
for(int i=1; i<n; i++){
if(i==a) continue;
dista[i] = getDistance(a, i);
if(dista[i] > dista[b]){
b=i;
}
}
vector<int> distb(n);
distb[0] = dist0[b];
distb[a] = dista[b];
for(int i=1; i<n; i++){
if(i==a || i==b) continue;
distb[i] = getDistance(b, i);
}
int diameter = dista[b];
//group the leafes
vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter;
vector<int> ddiam(n); ddiam[a]=ddiam[b]=0;
map<int, vector<int> > group;
for(int i=0; i<n; i++){
if(i==a || i==b) continue;
ddiam[i] = (dista[i]+distb[i] - diameter)/2;
dleft[i] = dista[i]-ddiam[i];
group[dleft[i]].push_back(i);
}
//compute r
int r=diameter;
for(auto [x, g]: group){
r = min(r, max(x, diameter-x));
}
return r;
}
컴파일 시 표준 에러 (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... |