제출 #599251

#제출 시각아이디문제언어결과실행 시간메모리
599251sofapuden도시들 (IOI15_towns)C++17
25 / 100
21 ms1036 KiB
#include "towns.h" #include<bits/stdc++.h> using namespace std; vector<vector<int>> Q; void que(int a, int b){ if(Q[a][b] != -1)return; Q[a][b] = Q[b][a] = getDistance(a,b); } int hubDistance(int N, int sub) { Q.clear(); Q.resize(N,vector<int>(N,-1)); for(int i = 0; i < N; ++i)Q[i][i] = 0; int mx = -1; int ind = sub; for(int i = 0; i < N; ++i){ que(0,i); if(Q[0][i] > mx){ mx = Q[0][i]; ind = i; } } int mx2 = -1; int ind2 = sub; for(int i = 0; i < N; ++i){ que(ind,i); if(Q[ind][i] > mx2){ mx2 = Q[ind][i]; ind2 = i; } } for(int i = 0; i < N; ++i){ que(ind2,i); } int ans = 1<<30; for(int i = 0; i < N; ++i){ ans = min(ans,abs(Q[ind][i]-Q[ind2][i])); } return (ans+Q[ind][ind2]+1)/2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...