이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// full
#include <bits/stdc++.h>
using namespace std;
int getDistance(int i, int j);
int hubDistance(int N, int sub){
int n = N,a = 0, b = 0, r = 1e9; vector<vector<int>> dist(n,vector<int>(n,-1));
auto get = [&](int x, int y){
if(x == y) return 0;
if(x > y) swap(x,y);
if(dist[x][y] != -1) return dist[x][y];
return dist[x][y] = getDistance(x,y);
};
for(int i = 0; i < n; i++){
if(get(0,i) > get(0,a)){
a = i;
}
}
for(int i = 0; i < n; i++){
if(get(a,i) > get(a,b)){
b = i;
}
}
map<int,vector<int>> mp;
for(int i = 0; i < n; i++){
int da = (get(a,0) + get(a,i) - get(0,i)) / 2;
r = min(r,max(da,get(a,b)-da));
mp[da].emplace_back(i);
}
set<int> lft,rit;
for(int i = 0; i < n; i++) rit.insert(i);
int pre = 0, suf = n;
for(auto&[da,vec]:mp){
suf -= vec.size();
for(int u : vec) rit.erase(u);
if(suf <= n/2 && pre <= n/2 && r == max(da,get(a,b)-da)){
set<int> s(vec.begin(),vec.end());
auto same = [&](int x, int y){
if(s.find(x) == s.end() && s.find(y) == s.end()){
return bool(lft.find(x) == lft.end()) == bool(lft.find(y) == lft.end());
} else if(s.find(x) == s.end() || s.find(y) == s.end()) return false;
return get(a,x) + get(a,y) - get(x,y) > 2*r;
};
vector<int> ls,bk;
for(int u : vec){
if(ls.empty() || !same(ls.back(),u)){
ls.emplace_back(u);
if(bk.size()){
ls.emplace_back(bk.back());
bk.pop_back();
}
} else{
bk.emplace_back(u);
}
}
int t = ls.back(),sz = 0; bool maj = 0;
while(ls.size()){
if(same(ls.back(),t)){
if(ls.size() == 1){
maj = 1;
sz++;
break;
}
sz++;
ls.pop_back(); ls.pop_back();
} else{
ls.pop_back();
if(bk.empty()){
maj = 0;
break;
}
sz++;
bk.pop_back();
}
}
sz += bk.size();
if(bk.size()) maj = 1;
return (sz <= n/2 ? 1 : -1) * r;
}
pre += vec.size();
for(int u : vec) lft.insert(u);
}
return r;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:34:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
34 | suf -= vec.size();
| ^
towns.cpp:76:27: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
76 | sz += bk.size();
| ^
towns.cpp:56:44: warning: variable 'maj' set but not used [-Wunused-but-set-variable]
56 | int t = ls.back(),sz = 0; bool maj = 0;
| ^~~
towns.cpp:81:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
81 | pre += vec.size();
| ^
towns.cpp:6:28: warning: unused parameter 'sub' [-Wunused-parameter]
6 | 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... |