Submission #1242853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242853		efishel	Towns (IOI15_towns)	C++20	Compilation error	0 ms	0 KiB

towns

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 120;
int dis[MAXN][MAXN];

int getDistance (int i, int j) {
    return dis[i][j];
}

int hubDistance (int N, int sub) {
    ll n = N;
    ll u1 = 0, dis1 = 0;
    for (ll u = 1; u < n; u++) {
        ll dis = getDistance(0, u);
        if (dis <= dis1) continue;
        dis1 = dis;
        u1 = u;
    }
    vll disU1(n, 0), disU2(n, 0);
    map <ll, vll> mp1, mp2;
    ll u2 = 0, diam = dis1;
    mp1[0].push_back(dis1);
    disU1[0] = dis1;
    for (ll u = 1; u < n; u++) {
        if (u == u1) continue;
        ll dis = getDistance(u1, u);
        disU1[u] = dis;
        mp1[dis].push_back(u);
        if (dis <= diam) continue;
        diam = dis;
        u2 = u;
    }
    // cerr << u1 << ' ' << u2 << '\n';
    disU2[u1] = disU1[u2];
    for (ll u = 0; u < n; u++) {
        if (u == u1 || u == u2) continue;
        disU2[u] = getDistance(u2, u);
    }
    for (ll u = 0; u < n; u++) {
        ll ext = (disU1[u] - disU2[u] + diam) / 2;
        mp2[ext].push_back(u);
    }
    ll ans = diam;
    for (auto [d, ve] : mp2) {
        ans = min(ans, max(d, diam-d));
    }
    bool existsBal = false;
    ll lhs = 0;
    for (auto [d, ve] : mp2) {
        if (ans != max(d, diam-d)) { lhs += ve.size(); continue; }
        ll rhs = n-lhs-ve.size();
        if (lhs > n/2 || rhs > n/2 || ve.size() > n/2) { lhs += ve.size(); continue; }
        existsBal = true;
        lhs += ve.size();
    }
    return (existsBal ? ans : -ans);
    // for (auto [d, ve] : mp2) {
    //     cerr << d << ": ";
    //     for (ll u : ve) cerr << u << ' ';
    //     cerr << '\n';
    // }
    // return 0;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n; cin >> n; for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) cin >> dis[i][j];
    cout << hubDistance(n, -1) << '\n';
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccjSgdKf.o: in function `getDistance(int, int)':
grader.c:(.text+0x110): multiple definition of `getDistance(int, int)'; /tmp/cc8t6d7u.o:towns.cpp:(.text+0x60): first defined here
/usr/bin/ld: /tmp/ccjSgdKf.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8t6d7u.o:towns.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status