# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52096 |
2018-06-23T21:15:43 Z |
kingpig9 |
Towns (IOI15_towns) |
C++11 |
|
28 ms |
724 KB |
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 115;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
template<class T>
void setmax (T &a, T b) {
if (a < b) {
a = b;
}
}
template<class T>
void setmin (T &a, T b) {
if (b < a) {
a = b;
}
}
int N;
int dist[MAXN][MAXN];
int getdist (int x, int y) {
assert(0 <= x && x < N);
assert(0 <= y && y < N);
if (x == y) {
return 0;
}
if (x > y) {
swap(x, y);
}
if (dist[x][y] == 0) {
dist[x][y] = getDistance(x, y);
}
return dist[x][y];
}
int getcent (int a, int b, int c) {
//distance from a to center(a, b, c)
return (getdist(a, b) + getdist(a, c) - getdist(b, c)) / 2;
}
int diamx, diamy, diam;
int dxcent;
int ans;
int distl[MAXN]; //distance to left of diameter
map<int, int> mp, psum; //map of branches sizes, prefix sums
void reset() {
fillchar(dist, 0);
diamx = diamy = diam = ans = 0;
for (int i = 0; i < MAXN; i++) {
distl[i] = 0;
}
mp.clear();
psum.clear();
}
pii getfar (int x) {
pii f(0, x);
for (int i = 0; i < N; i++) {
setmax(f, pii(getdist(i, x), i));
}
return f;
}
void calc_diam() {
pii far0 = getfar(0);
diamx = far0.se;
tie(diam, diamy) = getfar(diamx);
dxcent = getcent(diamx, 0, diamy);
ans = diam;
}
void calc_branches() {
//map of branch sizes
for (int i = 0; i < N; i++) {
int d = min(getcent(diamx, 0, i), dxcent);
setmin(ans, max(d, diam - d));
distl[i] = d;
mp[d]++;
}
//prefix sum
int p = 0;
for (auto it : mp) {
p += it.se;
psum[it.fi] = p;
}
}
bool same (int a, int b) {
return a == b || getcent(diamx, a, b) > distl[a];
}
bool has_balanced_hub() {
vector<int> vlist, vbucket;
//phase 1
for (int leaf = 0; leaf < N; leaf++) {
if (!vlist.empty() && same(vlist.back(), leaf)) {
//same
vbucket.push_back(leaf);
} else {
//not same
vlist.push_back(leaf);
if (!vbucket.empty()) {
vlist.push_back(vbucket.back());
vbucket.pop_back();
}
}
}
//phase 2
int maj = vlist.back();
while (!vlist.empty()) {
if (same(vlist.back(), maj)) {
if (vlist.size() == 1) {
vbucket.push_back(vlist.back());
vlist.pop_back();
} else {
vlist.pop_back();
vlist.pop_back();
}
} else {
vlist.pop_back();
if (vbucket.empty()) {
//there is no majority element
break;
}
vbucket.pop_back();
}
}
if (!vbucket.empty()) {
return false; //there is a majority element
}
//no majority element -- but may still not be OK
for (auto it : mp) {
int dl = it.fi, dr = diam - dl;
if (max(dl, dr) == ans) {
//check if this is balanced -- the branches are balanced, but the left/right w.r.t the diameter may not be
int lsize = prev(psum.find(dl))->se;
int csize = it.se;
int rsize = N - lsize - csize;
if (lsize <= N / 2 && rsize <= N / 2) {
return true;
}
}
}
return false;
}
int hubDistance (int nnnnn, int shostakovich) {
reset();
N = nnnnn;
calc_diam();
calc_branches();
return has_balanced_hub() ? ans : -ans;
}
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:166:33: warning: unused parameter 'shostakovich' [-Wunused-parameter]
int hubDistance (int nnnnn, int shostakovich) {
^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
376 KB |
Output is correct |
2 |
Correct |
19 ms |
484 KB |
Output is correct |
3 |
Correct |
2 ms |
484 KB |
Output is correct |
4 |
Correct |
21 ms |
536 KB |
Output is correct |
5 |
Correct |
21 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
720 KB |
Output is correct |
2 |
Correct |
16 ms |
720 KB |
Output is correct |
3 |
Correct |
21 ms |
720 KB |
Output is correct |
4 |
Correct |
21 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
720 KB |
Output is correct |
2 |
Correct |
20 ms |
720 KB |
Output is correct |
3 |
Correct |
2 ms |
720 KB |
Output is correct |
4 |
Correct |
21 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
720 KB |
Output is correct |
2 |
Correct |
24 ms |
724 KB |
Output is correct |
3 |
Correct |
21 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
724 KB |
Output is correct |
2 |
Correct |
22 ms |
724 KB |
Output is correct |
3 |
Correct |
28 ms |
724 KB |
Output is correct |