제출 #494694

#제출 시각아이디문제언어결과실행 시간메모리
494694thecodingwizard도시들 (IOI15_towns)C++11
13 / 100
93 ms1108 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; #define ii pair<int, int> #define mp make_pair int A, B; int dA, dB; map<ii, int> cached; int ct = 0; 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)]; ct++; return cached[mp(a, b)] = getDistance(a, b); } int isInA(int x) { return (getD(x, A) + getD(A, B) - getD(B, x)) / 2 < dA; } int isInB(int x) { return (getD(x, B) + getD(A, B) - getD(A, x)) / 2 < dB; } int getR(int x) { if (isInA(x) || isInB(x)) assert(false); return (getD(A, x) + getD(B, x) - getD(A, B)) / 2; } int hubDistance(int N, int sub) { ct = 0; cached.clear(); int maxDist = -1; A = -1; for (int i = 1; i < N; i++) { int d = getD(0, i); if (d > maxDist) { maxDist = d; A = i; } } maxDist = -1; B = -1; for (int i = 0; i < N; i++) { int d = getD(A, i); if (d > maxDist) { maxDist = d; B = i; } } int opt = 1e9; for (int i = 0; i < N; i++) { int distTo0 = getD(B, i); int distTo1 = getD(A, i); int dist0 = (maxDist + distTo0 - distTo1)/2; int dist1 = (maxDist + distTo1 - distTo0)/2; if (max(dist0, dist1) < opt) { opt = max(dist0, dist1); dA = dist1; dB = dist0; } } int mult = 1; int tot = 0; set<int> done; for (int i = 0; i < N; i++) { int sz = 0; if (isInA(i) || isInB(i)) continue; if (done.count(i)) continue; for (int j = 0; j < N; j++) { if (isInA(j) || isInB(j)) continue; if (getD(i, j) != getR(i) + getR(j)) { done.insert(j); sz++; } } tot += sz; if (sz > N/2) { mult = -1; } } int sz = 0; for (int i = 0; i < N; i++) { if (isInA(i)) { sz++; } } tot += sz; if (sz > N/2) mult = -1; sz = 0; for (int i = 0; i < N; i++) { if (isInB(i)) sz++; } tot += sz; if (sz > N/2) mult = -1; assert(tot == N); assert(ct <= N*(N-1)/2); return opt*mult; }

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

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:33:28: warning: unused parameter 'sub' [-Wunused-parameter]
   33 | 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...