제출 #557702

#제출 시각아이디문제언어결과실행 시간메모리
557702sidon도시들 (IOI15_towns)C++17
100 / 100
25 ms616 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; int hubDistance(int N, int _) { int d[200][200] {}, x {}; for(int i = 1; i < N; ++i) if((d[0][i] = getDistance(0, i)) > d[0][x]) x = i; int y = x; for(int i = 0; i < N; ++i) if((d[x][i] = getDistance(x, i)) > d[x][y]) y = i; int R = 1e6, c[N], h = -1; array<int, 2> cR {R}; for(int i = 0; i < N; ++i) { c[i] = (d[x][i] - d[0][i] + d[0][x]) / 2; R = min(R, max(c[i], d[x][y] - c[i])); if(i && i != x) { cR[0] = min(cR[0], c[i]); cR[1] = max(cR[1], c[i]); } } for(int i = 0; i < N; ++i) if(R == max(c[i], d[x][y] - c[i])) { int cnt[2] {}; for(int j = 0; j < N; ++j) if(c[i] != c[j]) ++cnt[c[j] > c[i]]; while(!(cnt[0] + cnt[1])); if(max(cnt[0], cnt[1]) <= N/2) h = i; } if(h < 0) return -R; c[0] = cR[1], c[x] = cR[0]; d[x][x] = 2 * c[x]; auto same = [&](int i, int j) { return i == j || getDistance(i, j) < d[x][i] + d[x][j] - 2 * c[h]; }; int cnt {}, val {}, w[N] {}; map<int, bool> bad; for(int i = 0; i < N; ++i) if(c[i] == c[h]) { if(!cnt) val = i, bad.clear(); if(same(i, val)) ++cnt, ++w[val]; else --cnt, w[i] = 1, bad[i] = 1; } cnt = 0; for(int i = 0; i < N; ++i) if(!bad[i] && w[i] && same(i, val)) cnt += w[i]; return cnt > N/2 ? -R : R; }

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

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