이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int hubDistance(int N, int sub) {
map<pair<int,int>,int> mpp;
function<int(int,int)> get=[&](int a,int b){
if(a==b) return 0;
if(a>b) swap(a,b);
if(mpp.find({a,b})!=mpp.end()) return mpp[{a,b}];
else{
mpp[{a,b}]=getDistance(a,b);
return mpp[{a,b}];
}
};
int n=N;
vector<int> dis(n),dis2(n);
for(int i=0;i<n;i++){
dis2[i]=get(0,i);
}
int x=max_element(all(dis2))-dis2.begin();
for(int i=0;i<n;i++){
dis[i]=get(x,i);
}
int R=*max_element(all(dis));
int y=0;
vector<int> val1(n),val2(n);
vector<int> vec;
for(int i=0;i<n;i++){
vec.push_back(dis[i]-(dis[i]+dis2[i]-dis[y])/2);
val1[i]=dis[i]-(dis[i]+dis2[i]-dis[y])/2;
val2[i]=(dis[i]+dis2[i]-dis[y])/2;
}
sort(all(vec));
int ans=R;
for(auto v:vec){
ans=min(ans,max(v,R-v));
}
map<int,int> mp;
for(auto v:vec){
mp[v]++;
}
bool tf=false;
int pre=0;
for(auto v:mp){
if(max(v.f,R-v.f)==ans){
int mx=max({pre,v.s,n-pre-v.s});
if(mx<=n/2){
tf=true;
}
}
pre+=v.s;
}
return (tf?ans:-ans);
function<bool(int,int)> same=[&](int a,int b){
int d=get(a,b);
return (d==(val2[a]+val2[b]));
};
if(!tf){
pre=0;
for(auto v:mp){
if(max(v.f,R-v.f)==ans){
if(v.s>n/2){
vector<int> xs;
for(int i=0;i<n;i++){
if(val1[i]==v.f){
xs.push_back(i);
}
}
mt19937 rng(time(NULL));
uniform_int_distribution<int> gen(0,(int)xs.size()-1);
tf=true;
for(int t=0;t<2;t++){
int pos=gen(rng);
int cnt=0;
for(int i=0;i<(int)xs.size();i++){
if(i==pos){
cnt++;
continue;
}
if(same(xs[i],xs[pos])) cnt++;
}
if(cnt>n/2){
tf=false;
break;
}
}
}
}
pre+=v.s;
}
}
return (tf?ans:-ans);
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:29:33: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
29 | int x=max_element(all(dis2))-dis2.begin();
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
towns.cpp:13:28: warning: unused parameter 'sub' [-Wunused-parameter]
13 | 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... |