Submission #553577

#	Time	Username	Problem	Language	Result	Execution time	Memory
553577		elazarkoren	Towns (IOI15_towns)	C++17	100 / 100	17 ms	932 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 105;

int dist[MAX_N][MAX_N];
int n;

int Dist(int v, int u) {
    if (u == v) return 0;
    if (dist[v][u] == -1) {
        dist[v][u] = dist[u][v] = getDistance(u, v);
    }
    return dist[v][u];
}

int dist_center[MAX_N];
bitset<MAX_N> interesting;

inline bool Same(int i, int j) {
    if (!interesting[i] || !interesting[j]) return false;
    return Dist(i, j) < dist_center[i] + dist_center[j];
}

bool CheckCentroid(int v, int d1, int u, int d2) {
    dist_center[v] = d1, dist_center[u] = d2;
    vi s;
    interesting.reset();
    for (int i = 0; i < n; i++) {
        if (i == v || i == u) continue;
        int a1 = Dist(v, u), a2 = Dist(v, i), a3 = Dist(u, i);
        int x, y, z;
        z = (a2 + a3 - a1) >> 1;
        x = a2 - z, y = a3 - z;
        if (x <= d1) {
            dist_center[i] = z + d1 - x;
        } else {
            dist_center[i] = z + d2 - y;
        }
        s.push_back(x);
        if (x == d1) interesting[i] = true;
    }
    s.push_back(0), s.push_back(d1 + d2);
    sort(all(s));
    if (n & 1 && s[n / 2] != d1) return false;
    if (!(n & 1) && s[n / 2] != d1 && s[n / 2 - 1] != d1) return false;
    if (interesting.count() <= n / 2) return true;
    stack<int> list, bucket;
    list.push(0);
    for (int i = 1; i < n; i++) {
        if (!Same(list.top(), i)) {
            list.push(i);
            if (!bucket.empty()) {
                list.push(bucket.top());
                bucket.pop();
            }
        } else {
            bucket.push(i);
        }
    }
    int x = list.top();
    while (!list.empty()) {
        if (Same(list.top(), x)) {
            if (list.size() == 1) {
                bucket.push(list.top());
                break;
            }
            list.pop();
        } else {
            if (bucket.empty()) return true;
            bucket.pop();
        }
        list.pop();
        if (bucket.empty() && !(list.size() & 1)) return true;
    }
    return bucket.empty();
}

int hubDistance(int N, int sub) {
    n = N;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = -1;
        }
    }
    pii p1 = {0, 0}, p2 = {0, 0}, q;
    for (int i = 1; i < n; i++) {
        q = {Dist(0, i), i};
        chkmax(p1, q);
    }
    int v = p1.y;
    for (int i = 0; i < n; i++) {
        q = {Dist(v, i), i};
        chkmax(p2, q);
    }
    int u = p2.y;
    int ans = dist[v][u];
    vii dists;
    for (int k = 1; k < n; k++) {
        if (k == v) continue;
        int a1 = Dist(v, 0), a2 = Dist(v, k), a3 = Dist(0, k);
        int x, y, z;
        z = (a2 + a3 - a1) >> 1;
        x = a2 - z, y = a3 - z;
        dists.push_back({x, y});
        chkmin(ans, max(x, dist[u][v] - x));
    }
    //if (sub <= 2) return ans;
    vii hubs;
    for (pii p : dists) {
        if (max(p.x, dist[u][v] - p.x) == ans) hubs.push_back(p);
    }
    sort(all(hubs));
    hubs.erase(unique(all(hubs)), hubs.end());
    for (pii p : hubs) {
        if (CheckCentroid(v, p.x, 0, p.y)) return ans;
    }
	return -ans;
}
/*
1 1
5
0 52 53 53 51
52 0 3 3 3
53 3 0 2 4
53 3 2 0 4
51 3 4 4 0
*/

/*
1 1
4
0 3 3 2
3 0 2 3
3 2 0 3
2 3 3 0
*/

Compilation message (stderr)

towns.cpp: In function 'bool CheckCentroid(int, int, int, int)':
towns.cpp:58:29: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     if (interesting.count() <= n / 2) return true;
      |         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:90:28: warning: unused parameter 'sub' [-Wunused-parameter]
   90 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 39 / 39