제출 #494881

#제출 시각아이디문제언어결과실행 시간메모리
494881thecodingwizard도시들 (IOI15_towns)C++11
26 / 100
120 ms1196 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; #define ii pair<int, int> #define mp make_pair #define inf 1e9; #define f first #define s second map<ii, int> cached; int getD(int a, int b) { if (a == b) return 0; if (a > b) swap(a, b); if (cached.count(mp(a, b))) return cached[mp(a, b)]; return cached[mp(a, b)] = getDistance(a, b); } int hubDistance(int N, int sub) { cached.clear(); int u, v; int maxDist = -1; for (int i = 0; i < N; i++) { if (getD(0, i) > maxDist) { maxDist = getD(0, i); u = i; } } maxDist = -1; for (int i = 0; i < N; i++) { if (getD(u, i) > maxDist) { maxDist = getD(u, i); v = i; } } int radius = inf; int d1 = -1, d2 = -1; for (int i = 0; i < N; i++) { int distFromHubToU = (getD(u, i) + getD(u, 0) - getD(i, 0))/2; int distFromHubToV = getD(u, v) - distFromHubToU; if (max(distFromHubToU, distFromHubToV) < radius) { radius = max(distFromHubToU, distFromHubToV); d1 = distFromHubToU; d2 = -1; } else if (max(distFromHubToU, distFromHubToV) == radius) { if (distFromHubToU != d1) { d2 = distFromHubToU; } } } if (d2 != -1 && d1 > d2) swap(d1, d2); bool balanced = true; map<int, int> frequency; for (int i = 0; i < N; i++) { int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2; frequency[distFromU]++; } int ct1 = 0; int ct2 = 0; for (auto x : frequency) { if (x.f <= d1) ct1 += x.s; if (x.f <= d2) ct2 += x.s; } // cout << ct1 << " " << ct2 << " "<< d1 << " "<< d2 << endl; bool isHub2 = false; if (ct1 - frequency[d1] > N/2) balanced = false; if (ct1 < N/2) { if (d2 != -1) { if (ct2 - frequency[d2] <= N/2 && ct2 >= N/2) { isHub2 = true; } else balanced = false; } else { balanced = false; } } if (balanced) { int distToHub = -1; if (isHub2) { distToHub = d2; } else { distToHub = d1; } for (int i = 0; i < N; i++) { int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2; if (distFromU != distToHub) continue; int sz = 1; for (int j = 0; j < N; j++) { int distFromU = (getD(u, j) + getD(u, 0) - getD(0, j))/2; if (distFromU != distToHub) continue; if (getD(i, u) + getD(j, u) - getD(i, j) != distToHub*2) { sz++; } } if (sz > N/2) balanced = false; } } return (balanced ? 1 : -1) * radius; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:96:21: warning: declaration of 'distFromU' shadows a previous local [-Wshadow]
   96 |                 int distFromU = (getD(u, j) + getD(u, 0) - getD(0, j))/2;
      |                     ^~~~~~~~~
towns.cpp:92:17: note: shadowed declaration is here
   92 |             int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2;
      |                 ^~~~~~~~~
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
   20 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp:98:38: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |                 if (getD(i, u) + getD(j, u) - getD(i, j) != distToHub*2) {
      |                                  ~~~~^~~~~~
towns.cpp:45:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |         int distFromHubToV = getD(u, v) - distFromHubToU;
      |                              ~~~~^~~~~~
#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...