제출 #96587

#제출 시각아이디문제언어결과실행 시간메모리
96587streifi도시들 (IOI15_towns)C++14
25 / 100
25 ms1912 KiB
#include "towns.h" #include <vector> #include <iostream> using namespace std; const int MAX_DIST = 1e6+5; vector< vector<int> > mat; int get_dist(int a, int b) { if (mat[a][b] == -1) return mat[a][b] = mat[b][a] = getDistance(a, b); else return mat[a][b]; } int hubDistance(int N, int sub) { mat.assign(N, vector<int>(N, -1)); int u = -1; int mx = -1; for (int i = 0; i < N; ++i) { if (get_dist(0, i) > mx) { u = i; mx = get_dist(0, i); } } int v = -1; mx = -1; for (int i = 0; i < N; ++i) { if (get_dist(u, i) > mx) { v = i; mx = get_dist(u, v); } } //cout << u << " " << v << endl; vector<int> freq(mx+1, 0); for (int i = 0; i < N; ++i) { int k = get_dist(i, u); int l = get_dist(i, v); ++freq[(mx+k-l)/2]; } int ans = 0x3f3f3f3f; bool bal; vector<int> cum(mx+2), cumr(mx+2); cum[0] = 0; cum[mx+1] = 0; for (int i = 0 ; i < mx; ++i) { cum[i+1] = cum[i]+freq[i]; cumr[mx-i] = cumr[mx-i+1]+freq[mx-i]; } for (int i = 0; i < mx; ++i) { //cout << freq[i] << " "; if (freq[i] && max(i, mx-i) <= ans) { if (max(i, mx-i) < ans) { ans = max(i, mx-i); bal = false; } if (!bal) { if (max(freq[i], max(cum[i], cumr[i])) <= N/2) bal = true; } } } //cout << endl; if (!bal) ans *= -1; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:18:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~
towns.cpp:65:2: warning: 'bal' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (!bal) ans *= -1;
  ^~
#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...