이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 tgt = 0;
vector<int> stackA, stackB;
stackB.pb(0);
for (int i = 0; i < nodes.size() - 1; i++) {
int a = nodes[tgt], b = nodes[i+1];
bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2;
if (same) {
stackB.pb(i+1);
} else {
stackA.pb(stackB.back());
stackB.pop_back();
if (stackB.empty()) {
tgt = i+1;
stackB.pb(i+1);
} else {
stackA.pb(i+1);
}
}
}
if (tgt < nodes.size()) {
int sz = stackB.size();
while (!stackA.empty()) {
int x = stackA.back();
stackA.pop_back();
int a = nodes[x], b = nodes[tgt];
bool same = getD(a, u) + getD(b, u) - getD(a, b) != distToHub*2;
if (same) {
sz++;
if (!stackA.empty()) stackA.pop_back();
} else {
if (stackB.empty()) break;
stackB.pop_back();
}
}
if (sz > N/2) balanced = false;
}
}
return (balanced ? 1 : -1) * radius;
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i = 0; i < nodes.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~~
towns.cpp:118:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | if (tgt < nodes.size()) {
| ~~~~^~~~~~~~~~~~~~
towns.cpp:119:33: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
119 | int sz = stackB.size();
| ~~~~~~~~~~~^~
towns.cpp:21:28: warning: unused parameter 'sub' [-Wunused-parameter]
21 | int hubDistance(int N, int sub) {
| ~~~~^~~
towns.cpp:124:46: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |