Submission #553527

#	Time	Username	Problem	Language	Result	Execution time	Memory
553527		elazarkoren	Towns (IOI15_towns)	C++17	13 / 100	15 ms	396 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];
}

struct Dsu{
    vi par, sz;
    Dsu(int n) {
        par.resize(n), sz.resize(n, 1);
        iota(all(par), 0);
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return;
        if (sz[pa] < sz[pb]) swap(pa, pb);
        par[pb] = pa;
        sz[pa] += sz[pb];
    }
};

int dist_center[MAX_N];

inline bool Same(int i, int j) {
    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;
    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);
    }
    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 / 1] == d1 && s[(n + 1) / 2] == d1) return false;
    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();
    }
    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 = 0; k < n; k++) {
        if (k == v || k == u) continue;
        int a1 = Dist(v, u), a2 = Dist(v, k), a3 = Dist(u, 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, y));
    }
    //if (sub <= 2) return ans;
    vii hubs;
    for (pii p : dists) {
        if (max(p.x, p.y) == ans) hubs.push_back(p);
    }
    sort(all(hubs));
    hubs.erase(unique(all(hubs)), hubs.end());
    for (pii p : hubs) {
        if (CheckCentroid(v, p.x, u, 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
*/

Compilation message (stderr)

towns.cpp: In constructor 'Dsu::Dsu(int)':
towns.cpp:30:13: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   30 |     Dsu(int n) {
      |         ~~~~^
towns.cpp:18:5: note: shadowed declaration is here
   18 | int n;
      |     ^
towns.cpp: In constructor 'Dsu::Dsu(int)':
towns.cpp:30:13: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   30 |     Dsu(int n) {
      |         ~~~~^
towns.cpp:18:5: note: shadowed declaration is here
   18 | int n;
      |     ^
towns.cpp: In constructor 'Dsu::Dsu(int)':
towns.cpp:30:13: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   30 |     Dsu(int n) {
      |         ~~~~^
towns.cpp:18:5: note: shadowed declaration is here
   18 | int n;
      |     ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:102:28: warning: unused parameter 'sub' [-Wunused-parameter]
  102 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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