제출 #494883

#제출 시각아이디문제언어결과실행 시간메모리
494883thecodingwizard도시들 (IOI15_towns)C++11
13 / 100
17 ms368 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 #define pb push_back 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; } vector<int> nodes; for (int i = 0; i < N; i++) { int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2; if (distFromU != distToHub) continue; nodes.pb(i); } int ctr = 1; int tgt = 0; for (int i = 0; i < nodes.size() - 1; i++) { int a = nodes[i], b = nodes[i+1]; bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2; if (same) { ctr++; } else { ctr--; } if (ctr == 0) { ctr = 1; tgt = i+1; } } if (tgt < nodes.size()) { int sz = 0; for (int i = 0; i < nodes.size(); i++) { int a = nodes[i], b = tgt; bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2; if (same) { sz++; } } if (sz > N/2) balanced = false; } } return (balanced ? 1 : -1) * radius; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int i = 0; i < nodes.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
towns.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if (tgt < nodes.size()) {
      |             ~~~~^~~~~~~~~~~~~~
towns.cpp:116:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             for (int i = 0; i < nodes.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~
towns.cpp:21:28: warning: unused parameter 'sub' [-Wunused-parameter]
   21 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp:118:46: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |                 bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2;
      |                                          ~~~~^~~~~~
towns.cpp:46:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |         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...