이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> distv;
int n;
int gd;
int dist(int a, int b){
if (a==b){return 0;}
if (a>b){
swap(a,b);
}
if (distv[a][b]!=-1){
return distv[a][b];
} else {
gd++;
assert(gd<=(n*(n-1))/2);
return distv[a][b]=getDistance(a,b);
}
}
int grab(int s){
int hd = 0;
int adist = -1;
int aind = -1;
for (int i = 0; i<n; i++){
int ds = dist(1,i);
if (adist<ds){
adist=ds;
aind=i;
}
}
int bdist = -1;
int bind = -1;
for (int i = 0; i<n; i++){
int ds = dist(aind,i);
if (bdist<ds){
bdist=ds;
bind=i;
}
}
bool exists = true;
//from adist to aind
//vector<int> diameter;
int hubdist = 1e9;
vector<int> hubposs;
for (int i = 0; i<n; i++){
if (i==aind||i==bind){continue;}
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
int rv = max(distfroma,dist(aind,bind)-distfroma);
if (rv<hubdist){
hubdist=rv;
hubposs.clear();
hubposs.push_back(i);
} else if (rv==hubdist){
hubposs.push_back(i);
}
}
for (int hubind : hubposs){
//cout<<"hub: "<<hubind<<'\n';
hd=hubdist;
int hubfroma = dist(aind,hubind)-(dist(aind,hubind)+dist(bind,hubind)-dist(aind,bind))/2;;
vector<int> nodesinhub;
int befcnt=0;
int aftcnt=0;
for (int i = 0; i<n; i++){
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
if (distfroma<hubfroma){
befcnt++;
} else if (distfroma==hubfroma){
nodesinhub.push_back(i);
} else {
aftcnt++;
}
}
//cout<<befcnt<<' '<<aftcnt<<' '<<nodesinhub.size()<<'\n';
if (befcnt>n/2||aftcnt>n/2){exists=false;continue;}
if (s==4){
if (nodesinhub.size()>n/2){exists=false;continue;}
else {return hd;}
}
/*vector<bool> visited(n,false);
int nodesleft = nodesinhub.size();
for (int i : nodesinhub){
if (visited[i]){continue;}
if (nodesleft<=n/2){exists=true;break;}
int nodesingrp = 1;
visited[i]=true;
for (int j : nodesinhub){
if (!visited[j]){
if (dist(i,j)<dist(aind,i)+dist(aind,j)-2*hubfroma){
nodesingrp++;
visited[j]=true;
}
}
}
//cout<<nodesingrp<<'\n';
if (nodesingrp>n/2){exists=false;break;}
nodesleft-=nodesingrp;
}
if (exists){
return hd;
}*/
int el = nodesinhub[0];
int cnt = 0;
for (int i : nodesinhub){
if (cnt==0){
el = i;
cnt++;
} else if (dist(el,i)<dist(aind,i)+dist(aind,el)-2*hubfroma){
// same
cnt++;
} else {
cnt--;
}
}
int eltot = 0;
for (int i : nodesinhub){
if (dist(el,i)<dist(aind,i)+dist(aind,el)-2*hubfroma){
eltot++;
}
}
if (eltot<=n/2){
return hd;
}
}
return -hd;
}
int hubDistance(int N, int sub) {
gd=0;
n=N;
distv.assign(n,vector<int>(n,-1));
if (sub>2){return grab(sub);}
int adist = -1;
int aind = -1;
for (int i = 0; i<n; i++){
int ds = dist(1,i);
if (adist<ds){
adist=ds;
aind=i;
}
}
int bdist = -1;
int bind = -1;
for (int i = 0; i<n; i++){
int ds = dist(aind,i);
if (bdist<ds){
bdist=ds;
bind=i;
}
}
//from adist to aind
//vector<int> diameter;
int hubdist = 1e9;
int hubind = -1;
for (int i = 0; i<n; i++){
if (i==aind||i==bind){continue;}
int distfroma = dist(aind,i)-(dist(aind,i)+dist(bind,i)-dist(aind,bind))/2;
int rv = max(distfroma,dist(aind,bind)-distfroma);
if (rv<hubdist){
hubdist=rv;
hubind=i;
}
}
return hubdist;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int grab(int)':
towns.cpp:83:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
83 | if (nodesinhub.size()>n/2){exists=false;continue;}
| ~~~~~~~~~~~~~~~~~^~~~
towns.cpp:46:10: warning: variable 'exists' set but not used [-Wunused-but-set-variable]
46 | bool exists = true;
| ^~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:165:9: warning: variable 'hubind' set but not used [-Wunused-but-set-variable]
165 | int hubind = -1;
| ^~~~~~
# | 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... |