제출 #835484

#제출 시각아이디문제언어결과실행 시간메모리
835484Valaki2도시들 (IOI15_towns)C++14
13 / 100
14 ms484 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)); } bool from_X = false, from_Y = false; for(int i = 1; i <= n; i++) { if(i == X || i == Y) { continue; } int a = dist(i, X); int b = dist(i, Y); int from = (a + b - diam) / 2; if(a - from == ans) { from_X = true; } else if(b - from == ans) { from_Y = true; } } vector<int> Z = {X, Y}; int idx = 0; if(from_Y) { idx = 1; } set<int> s; int less_cnt = 0, more_cnt = 0; for(int i = 1; i <= n; i++) { int a = dist(i, X); int b = dist(i, Y); int from = (a + b - diam) / 2; vector<int> d = {a - from, b - from}; if(d[idx] == ans) { s.insert(i); } if(d[idx] < ans) { less_cnt++; } if(d[idx] > ans) { more_cnt++; } } if(less_cnt > n / 2 || more_cnt > n / 2) { return -ans; } if(from_X && from_Y) { return ans; } vector<int> di(1 + n, 0); for(int i : s) { int a = dist(i, X); int b = dist(i, Y); int from = (a + b - diam) / 2; di[i] = from; } for(int i : s) { for(int j : s) { int dij = dist(i, j); int cnt = 0; if(dij < di[i] + di[j]) { cnt++; } if(cnt > n / 2) { return -ans; } } } return ans; }

컴파일 시 표준 에러 (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...