이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
const ll maxn=1e18;
ll to0[120],tor1[120],tor2[120],gf[120][120],n;
ll r1,r2;
int getd(int a,int b){
return gf[a][b];
}
struct DSU{
int val[120],sz[120];
void init(){
for(int i=0;i<n;i++)val[i]=i,sz[i]=1;
return;
}
int f(int a){
if(a==val[a])return a;
val[a]=f(val[a]);
return val[a];
}
void onion(int a,int b){
a=f(a);
b=f(b);
if(a==b)return;
if(sz[a]>sz[b])swap(a,b);
val[a]=b;
sz[b]+=sz[a];
return;
}
}dsu;
int hubDistance(int N, int sub) {
n=N;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
gf[i][j]=getDistance(i,j);
gf[j][i]=gf[i][j];
}
}
for(int i=1;i<N;i++)to0[i]=getd(0,i);
ll maxn=0,pos=0;
for(int i=0;i<N;i++){
if(to0[i]>maxn){
maxn=to0[i];
pos=i;
}
}
r1=pos;
for(int i=0;i<N;i++)tor1[i]=getd(r1,i);
maxn=0,pos=0;
for(int i=0;i<N;i++){
if(tor1[i]>maxn){
maxn=tor1[i];
pos=i;
}
}
r2=pos;
vector<pair<ll,ll>> vc;
for(int i=0;i<N;i++){
ll dis=(to0[r1]+tor1[i]-to0[i])/2;
vc.push_back({dis,tor1[i]-dis});
}
ll ans=maxn;
for(int i=0;i<N;i++){
ans=min(ans,max(vc[i].F,tor1[r2]-vc[i].F));
}
vector<ll> want;
for(int i=0;i<N;i++){
if(ans==max(vc[i].F,tor1[r2]-vc[i].F)){
want.push_back(vc[i].F);
}
}
int ok=0;
for(auto dis:want){
int s=0,m=0,l=0;
vector<int> now;
for(int i=0;i<N;i++){
if(vc[i].F<dis)s++;
else if(vc[i].F==dis)now.push_back(i);
else l++;
}
if(s>N/2||l>N/2)continue;
int nx=now[0],mis=1,OK=1;
dsu.init();
for(int i=1,x=now[i];i<now.size();i++,x=now[i]){
if(nx==0){
mis=1;
nx=now[0];
continue;
}
if(getd(nx,x)<vc[nx].S+vc[x].S){
dsu.onion(nx,x);
mis++;
}else{
mis--;
}
if(mis==0)nx=0;
}
for(int i=0,x=now[i];i<now.size();i++,x=now[i]){
if(x==dsu.f(x)){
if(getd(nx,x)<vc[nx].S+vc[x].S){
dsu.onion(nx,x);
}
}
}
for(int i=0,x=now[i];i<now.size();i++,x=now[i]){
if(x==dsu.f(x)&&dsu.sz[x]>n/2){
OK=0;
}
}
ok|=OK;
}
return ok==1?ans:-ans;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int getd(int, int)':
towns.cpp:11:16: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
11 | return gf[a][b];
| ~~~~~~~^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:43:5: warning: declaration of 'maxn' shadows a global declaration [-Wshadow]
43 | ll maxn=0,pos=0;
| ^~~~
towns.cpp:7:10: note: shadowed declaration is here
7 | const ll maxn=1e18;
| ^~~~
towns.cpp:51:35: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
51 | for(int i=0;i<N;i++)tor1[i]=getd(r1,i);
| ^~
towns.cpp:87:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=1,x=now[i];i<now.size();i++,x=now[i]){
| ~^~~~~~~~~~~
towns.cpp:101:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for(int i=0,x=now[i];i<now.size();i++,x=now[i]){
| ~^~~~~~~~~~~
towns.cpp:108:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0,x=now[i];i<now.size();i++,x=now[i]){
| ~^~~~~~~~~~~
towns.cpp:77:11: warning: unused variable 'm' [-Wunused-variable]
77 | int s=0,m=0,l=0;
| ^
towns.cpp:115:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
115 | return ok==1?ans:-ans;
| ~~~~~^~~~~~~~~
towns.cpp:34:28: warning: unused parameter 'sub' [-Wunused-parameter]
34 | 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... |