Submission #1242854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242854		efishel	Towns (IOI15_towns)	C++20	35 / 100	9 ms	484 KiB

towns

#include "towns.h"
#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 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;
}

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