| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52084 |
2018-06-23T18:38:06 Z |
kingpig9 |
Towns (IOI15_towns) |
C++11 |
|
37 ms |
748 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 debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
#warning There can be more than one test case. Make sure you reset at every level.
template<class T>
void setmin (T &a, T b) {
if (b < a) {
a = b;
}
}
template<class T>
void setmax (T &a, T b) {
if (a < b) {
a = b;
}
}
int N;
int subtask;
int dist[MAXN][MAXN];
int getdist (int x, int y) {
assert(0 <= x);
assert(x < N);
assert(0 <= y);
assert(y < N);
if (x == y) {
return 0;
}
if (x > y) {
swap(x, y);
}
int &ref = dist[x][y];
if (ref) {
return ref;
}
return ref = getDistance(x, y);
}
array<int, 3> getcent (int a, int b, int c) {
//get distance to the meeting place of a, b, c
int dab = getdist(a, b), dac = getdist(a, c), dbc = getdist(b, c);
return array<int, 3> {(dab + dac - dbc) / 2, (dab - dac + dbc) / 2, (-dab + dac + dbc) / 2};
}
int diamx, diamy, diam;
int dxcent;
int ans;
map<int, vector<int>> mp;
map<int, int> psum; //prefix sum, suffix sum
int dl[MAXN];
void reset() {
fillchar(dist, 0);
diamx = diam = ans = 0;
mp.clear();
psum.clear();
}
pii getfar (int x) {
//farthest away
pii res(0, x);
for (int i = 0; i < N; i++) {
setmax(res, pii(getdist(i, x), i));
}
return res;
}
bool has_balanced_hub() {
vector<int> vlist, bucket;
for (int leaf = 0; leaf < N; leaf++) {
if (vlist.empty() || getcent(diamx, vlist.back(), leaf)[0] <= dl[vlist.back()]) {
//not equal
vlist.push_back(leaf);
if (!bucket.empty()) {
vlist.push_back(bucket.back());
bucket.pop_back();
}
//debug("noequal\n");
} else {
//equal
bucket.push_back(leaf);
//debug("siequal\n");
}
}
//check now whether it is a majority element
//More formally: "maj" = potential majority element. Nothing else could be a majority element. Check its count.
int maj = vlist.back(); //majority element
while (!vlist.empty()) {
int leaf = vlist.back();
if (leaf != maj && getcent(diamx, maj, leaf)[0] <= dl[maj]) {
//not equal
if (bucket.empty()) {
break;
}
bucket.pop_back();
vlist.pop_back();
} else {
//equal
if (vlist.size() == 1) {
bucket.push_back(vlist[0]);
vlist.pop_back();
} else {
vlist.pop_back();
vlist.pop_back();
}
}
}
if (!bucket.empty()) {
//there is a majority element
//debug("bucket not empty --> there is majority element\n");
return false;
}
//even without majority element, there may still be something wrong.
//debug("there may still be something wrong without majority element...\n");
for (auto it : mp) {
int lt = it.fi, rt = diam - lt; //bad names of variables...
if (lt == 0 || rt == 0) {
continue;
}
if (max(lt, rt) == ans) {
auto pit = prev(psum.find(lt));
vector<int> leaves = it.se;
int lsize = pit->se;
int csize = leaves.size();
int rsize = N - lsize - csize;
if (lsize <= N / 2 && rsize <= N / 2) {
return true;
}
}
}
return false;
}
int go() {
pii far0 = getfar(0);
pii farx = getfar(far0.se);
diamx = far0.se;
diamy = farx.se; //don't actually use this for querying.
diam = farx.fi;
debug("diameter: %d -> %d, distance %d\n", diamx, diamy, diam);
ans = diam;
dxcent = getcent(diamx, 0, diamy)[0];
debug("distance from diamx = %d to CENTER is %d\n", diamx, dxcent);
//note that this starts at ONE, not 0.
for (int i = 0; i < N; i++) {
int d = min(getcent(diamx, 0, i)[0], dxcent);
debug("i = %d, d = %d\n", i, d);
mp[d].push_back(i);
setmin(ans, max(d, diam - d));
dl[i] = d;
}
for (auto it = mp.begin(); it != mp.end(); it++) {
psum[it->fi] = it->se.size();
if (it != mp.begin()) {
psum[it->fi] += psum[prev(it)->fi];
}
}
return has_balanced_hub() ? ans : -ans;
}
int hubDistance (int nnn, int subbbb) {
#warning reset totally global variables
N = nnn;
subtask = subbbb;
reset();
return go();
}
Compilation message
towns.cpp:17:2: warning: #warning There can be more than one test case. Make sure you reset at every level. [-Wcpp]
#warning There can be more than one test case. Make sure you reset at every level.
^~~~~~~
towns.cpp:192:2: warning: #warning reset totally global variables [-Wcpp]
#warning reset totally global variables
^~~~~~~
towns.cpp: In function 'bool has_balanced_hub()':
towns.cpp:150:27: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int csize = leaves.size();
~~~~~~~~~~~^~
towns.cpp: In function 'int go()':
towns.cpp:182:29: warning: conversion to 'std::map<int, int>::mapped_type {aka int}' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
psum[it->fi] = it->se.size();
~~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
340 KB |
Output is correct |
| 2 |
Correct |
18 ms |
488 KB |
Output is correct |
| 3 |
Correct |
3 ms |
540 KB |
Output is correct |
| 4 |
Correct |
24 ms |
540 KB |
Output is correct |
| 5 |
Correct |
26 ms |
652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
652 KB |
Output is correct |
| 2 |
Correct |
18 ms |
724 KB |
Output is correct |
| 3 |
Correct |
24 ms |
748 KB |
Output is correct |
| 4 |
Correct |
21 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
748 KB |
Output is correct |
| 2 |
Correct |
37 ms |
748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
748 KB |
Output is correct |
| 4 |
Correct |
36 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
748 KB |
Output is correct |
| 2 |
Correct |
32 ms |
748 KB |
Output is correct |
| 3 |
Correct |
21 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
748 KB |
Output is correct |
| 2 |
Correct |
23 ms |
748 KB |
Output is correct |
| 3 |
Correct |
23 ms |
748 KB |
Output is correct |
