제출 #586741

#제출 시각아이디문제언어결과실행 시간메모리
586741InternetPerson10도시들 (IOI15_towns)C++17
25 / 100
14 ms368 KiB
#include "towns.h" #include <bits/stdc++.h> typedef long long ll; using namespace std; map<pair<int, int>, int> distances; int getDist(int i, int j) { if(i == j) return 0; if(i > j) swap(i, j); if(distances.count({i, j})) { return distances[make_pair(i, j)]; } return distances[make_pair(i, j)] = getDistance(i, j); } vector<int> dists; map<ll, int> xs; int hubDistance(int n, int sub) { ll ans = 2e10; distances.clear(); dists.clear(); xs.clear(); dists.resize(n); int ma = -1, best = -1; for(int i = 0; i < n; i++) { dists[i] = getDist(0, i); if(ma < dists[i]) { ma = dists[i]; best = i; } } int x = best; ma = -1, best = -1; for(int i = 0; i < n; i++) { dists[i] = getDist(x, i); if(ma < dists[i]) { ma = dists[i]; best = i; } } int y = best; ll c = ma; for(int i = 0; i < n; i++) { if(i == x || i == y) continue; int a = getDist(x, i); int b = getDist(y, i); ans = min(ans, max(a + c - b, b + c - a)); if(!xs.count(a+c-b)) { xs[a+c-b] = 1; } else xs[a+c-b]++; } ans /= 2; ll cand = -1; int sum = 0; for(auto p : xs) { bool ok = (max(p.first, c - p.first) == (ll)ans); ok &= (sum <= n/2); sum += p.second; if(sub == 4) ok &= (p.second <= n/2); ok &= (n - sum <= n/2); if(ok) { if(sub == 4) return (int)ans; } } if(sub == 4) { return (int)-ans; } return (int)ans; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:57:8: warning: unused variable 'cand' [-Wunused-variable]
   57 |     ll cand = -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...