Submission #835456

#TimeUsernameProblemLanguageResultExecution timeMemory
835456Valaki2Towns (IOI15_towns)C++14
25 / 100
13 ms980 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; const int inf = 1e6 + 42; int n; vector<vector<int> > storedist; int dist(int a, int b) { if(storedist[a][b] != -1) { return storedist[a][b]; } return storedist[a][b] = storedist[b][a] = getDistance(a - 1, b - 1); } void reset() { storedist.clear(); storedist.assign(1 + n, vector<int> (1 + n, -1)); for(int i = 1; i <= n; i++) { storedist[i][i] = 0; } } int hubDistance(int N, int sub) { n = N; reset(); int ans = inf; int X = 1; for(int i = 2; i <= n; i++) { if(dist(1, i) > dist(1, X)) { X = i; } } int Y = X; for(int i = 1; i <= n; i++) { if(dist(X, i) > dist(X, Y)) { Y = i; } } int diam = dist(X, Y); for(int i = 1; i <= n; i++) { int a = dist(i, X); int b = dist(i, Y); int from = (a + b - diam) / 2; ans = min(ans, max(a - from, b - from)); } return ans; }

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:25:28: warning: unused parameter 'sub' [-Wunused-parameter]
   25 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
#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...