이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define vint vector<int>
using namespace std;
#ifndef x
#include "towns.h"
#else
vector<vint > formt(int m, vint v) {
vector<vint > x;
for(int i = 0; i < sz(v); ++i) {
if(sz(x) == 0 || sz(x.back()) == m) x.push_back({});
x.back().push_back(v[i]);
}
return x;
}
const int N = 102;
vector<array<int, 2> > v[N];
int dfsDist(int x, int y, int w = 0, int d = 0) {
if(x == y) return d;
for(auto z : v[x]) {
if(z[0] == w) continue;
int t = dfsDist(z[0], y, x, d + z[1]);
if(t) return t;
}
return 0;
}
vector<vector<int> > distArch;
int getDistance(int x, int y) {
if(0) return dfsDist(x, y);
else return distArch[x][y];
}
#endif
map<array<int, 2>, int> ma;
int dist(int x, int y) {
if(x == y) return 0;
if(x > y) swap(x, y);
if(!ma[{x, y}]) {
ma[{x, y}] = getDistance(x, y);
}
return ma[{x, y}];
}
int s;
int globz;
bool sameComponent(int x, int y) {
return dist(s, x) + dist(s, y) - dist(x, y) >> 1 > globz;
}
int majC(vint v) {
int cnt = 0;
vint lst, bckt;
for(int x : v) {
if(!sz(lst) || !sameComponent(x, lst.back())) {
lst.push_back(x);
if(sz(bckt)) {
lst.push_back(bckt.back());
bckt.pop_back();
}
} else {
bckt.push_back(x);
}
}
int t = lst.back();
while(sz(lst)) {
if(sameComponent(t, lst.back())) {
if(sz(lst) == 1) {
bckt.push_back(lst.back());
lst.pop_back();
} else {
lst.pop_back();
cnt += 1;
lst.pop_back();
}
} else {
if(!sz(bckt)) return 0;
bckt.pop_back();
cnt += 1;
lst.pop_back();
}
}
if(!sz(bckt)) return 0;
return cnt + sz(bckt);
}
int hubDistance(int n, int sub) {
if(sub > 2) assert(0);
ma.clear();
for(int i = 0, mx = 0; i < n; ++i) {
if(dist(0, i) > mx) {
mx = dist(0, i);
s = i;
}
}
// cout << "[s]: " << s << "\n";
int dm = 0;
for(int i = 0; i < n; ++i) {
dm = max(dm, dist(s, i));
}
vector<array<int, 2> > ytf;
for(int i = 1; i < n; ++i) {
if(i == s) continue;
int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
ytf.push_back({al, i});
}
vector<vector<int> > v;
sort(all(ytf));
int lmx = 0, rmn = 0;
for(int i = 0; i < sz(ytf); ++i) {
if(!i || ytf[i - 1][0] < ytf[i][0]) {
v.push_back({});
v.back().push_back(ytf[i][0]);
// cout << "\n" << ytf[i][0] << " -> ";
if(ytf[i][0] <= dm / 2) lmx = ytf[i][0];
else if(!rmn) rmn = ytf[i][0];
}
v.back().push_back(ytf[i][1]);
// cout << ytf[i][1] << " ";
}
if(!lmx) lmx = rmn;
else if(!rmn) rmn = lmx;
else if(dm - lmx < rmn) rmn = lmx;
else if(dm - lmx > rmn) lmx = rmn;
assert(lmx <= rmn);
int dr = -max(lmx, dm - lmx);
vint ftl(sz(v)), ftr(sz(v));
if(sz(v) > 1) {
ftl[1] = 1;
ftr[sz(v) - 2] = 1;
}
for(int i = 1; i < sz(v); ++i) {
ftl[i] += ftl[i - 1] + sz(v[i - 1]) - 1;
}
for(int i = sz(v) - 2; i >= 0; --i) {
ftr[i] += ftr[i + 1] + sz(v[i + 1]) - 1;
}
// cout << lmx << " " << rmn << endl;
for(int i = 0; i < sz(v); ++i) {
// cout << v[i][0] << endl;
if(v[i][0] == lmx || v[i][0] == rmn) {
// cout << ftl[i] << ", " << ftr[i] << endl;
if(ftl[i] > n / 2 || ftr[i] > n / 2) {
continue;
}
globz = v[i][0];
vector<int> t;
for(int j = 1; j < sz(v[i]); ++j) {
t.push_back(v[i][j]);
}
int x = majC(t);
if(x <= n / 2) dr = abs(dr);
}
}
return dr;
}
#ifdef x
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int sub, n;
sub = 1;
n = 11;
distArch = formt(n, vint{
0, 17, 18, 20, 17, 12, 20, 16, 23, 20, 11,
17, 0, 23, 25, 22, 17, 25, 21, 28, 25, 16,
18, 23, 0, 12, 21, 16, 24, 20, 27, 24, 17,
20, 25, 12, 0, 23, 18, 26, 22, 29, 26, 19,
17, 22, 21, 23, 0, 9, 21, 17, 26, 23, 16,
12, 17, 16, 18, 9, 0, 16, 12, 21, 18, 11,
20, 25, 24, 26, 21, 16, 0, 10, 29, 26, 19,
16, 21, 20, 22, 17, 12, 10, 0, 25, 22, 15,
23, 28, 27, 29, 26, 21, 29, 25, 0, 21, 22,
20, 25, 24, 26, 23, 18, 26, 22, 21, 0, 19,
11, 16, 17, 19, 16, 11, 19, 15, 22, 19, 0 });
cout << hubDistance(n, sub) << endl;
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'bool sameComponent(int, int)':
towns.cpp:52:33: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
52 | return dist(s, x) + dist(s, y) - dist(x, y) >> 1 > globz;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:111:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
111 | int al = dist(s, i) + dist(s, 0) - dist(0, i) >> 1;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
# | 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... |