이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//In the name of God
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
int d[3][maxn], dis[maxn], sz[maxn], h[maxn];
int solve3(int n){
return 0;
}
int solve4(int n){
ll v = 0;
for(ll i = 1; i < n; i++){
d[0][i] = getDistance(0, i);
if(d[0][i] > d[0][v]) v = i;
}
ll u = v;
for(ll i = 0; i < n; i++){
/*if(i == v) continue;
if(i == 0){
d[1][0] = d[0][v];
continue;
}*/
d[1][i] = getDistance(v, i);
if(d[1][i] > d[1][u]) u = i;
}
for(ll i = 0; i < n; i++){
/*if(i == u) continue;
if(i == 0){
d[2][0] = d[0][u];
continue;
}
if(i == v){
d[2][v] = d[1][u];
continue;
}*/
d[2][i] = getDistance(u, i);
}
ll D = d[1][u];
map<ll, ll> mp;
ll t = 1;
// cout << "# " << v << " " << u << "\n";
for(ll i = 0; i < n; i++){
h[i] = (d[1][i] + d[2][i] - D) / 2;
// cout << h[i] << " " << d[1][i] << " -> " << d[1][i] - h[i] << "\n";
if(!mp[d[1][i] - h[i]]){
mp[d[1][i] - h[i]] = t;
dis[t] = d[1][i] - h[i];
sz[t] = 0;
t++;
}
sz[mp[d[1][i] - h[i]]]++;
}
ll R = inf;
bool f = 0;
for(ll i = 1; i < t; i++){
R = min(R, max(dis[i], D - dis[i]));
if(sz[i] > n / 2) f = 1;
}
if(f) R *= -1;
return R;
}
int hubDistance(int n, int sub) {
if(sub == 3) return solve3(n);
return solve4(n);
}
/*int main(){
fast_io;
return 0;
}*/
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int solve3(int)':
towns.cpp:24:16: warning: unused parameter 'n' [-Wunused-parameter]
24 | int solve3(int n){
| ~~~~^
# | 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... |