Submission #1141495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141495		efishel	Towns (IOI15_towns)	C++20	0 / 100	1093 ms	27592 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>;
using vvll = vector <vll>;

const ll INF = ll(1E18)+16;

struct Info {
    ll u1, u2, u3;
    ll dis1, dis2, dis3;
    ll id;
};

struct DSU {
    vll par;
    vll sz;

    DSU (ll n): par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }

    ll find (ll u) {
        return u == par[u] ? u : par[u] = find(par[u]);
    }

    void join (ll u, ll v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        par[u] = v;
        sz[v] += sz[u];
    }
};

int hubDistance (int n, int sub) {
    vvll dis(n, vll(n, 0));
    for (ll i = 0; i < n; i++) {
        for (ll j = i+1; j < n; j++) {
            dis[i][j] = dis[j][i] = getDistance(i, j);
        }
    }
    auto fdiss = [&](ll u1, ll u2, ll u3) -> array <ll, 3> {
        ll d1 = dis[u1][u2], d2 = dis[u1][u3], d3 = dis[u2][u3];
        ll disU1 = (d3-d1-d2)/-2;
        ll disU2 = (d2-d1-d3)/-2;
        ll disU3 = (d1-d2-d3)/-2;
        return { disU1, disU2, disU3 };
    };
    // for (ll i: fdiss(0, 1, 2) )cerr<<i<< ' ';
    // cerr<<'\n';
    vector <Info> ve;
    ll id = 0;
    for (ll u1 = 0; u1 < n; u1++) {
        for (ll u2 = u1+1; u2 < n; u2++) {
            for (ll u3 = u2+1; u3 < n; u3++) {
                auto [dis1, dis2, dis3] = fdiss(u1, u2, u3);
                ve.push_back({ u1, u2, u3, dis1, dis2, dis3, id++ });
            }
        }
    }
    map <pair <ii, ii>, ll> mp;
    DSU dsu(id);
    for (auto [u1, u2, u3, dis1, dis2, dis3, id] : ve) {
        if (!mp.count({ { u1, dis1 }, { u2, dis2 } })) mp[{ { u1, dis1 }, { u2, dis2 } }] = id;
        if (!mp.count({ { u1, dis1 }, { u3, dis3 } })) mp[{ { u1, dis1 }, { u3, dis3 } }] = id;
        if (!mp.count({ { u2, dis2 }, { u3, dis3 } })) mp[{ { u2, dis2 }, { u3, dis3 } }] = id;
        ll &a = mp[{ { u1, dis1 }, { u2, dis2 } }];
        ll &b = mp[{ { u1, dis1 }, { u3, dis3 } }];
        ll &c = mp[{ { u2, dis2 }, { u3, dis3 } }];
        dsu.join(a, id);
        dsu.join(b, id);
        dsu.join(c, id);
    }
    map <ll, ll> mpAns;
    for (Info a : ve) {
        mpAns[dsu.find(a.id)] = max({ mpAns[dsu.find(a.id)], a.dis1, a.dis2, a.dis3 });
    }
    // for (Info a : ve) {
    //     if (a.u1 == 9 && a.dis1 == 13
    //      || a.u2 == 9 && a.dis2 == 13
    //      /* || a.u3 == 9 && a.dis3 == 13 */) cerr << dsu.find(a.id) << '\n';
    // }
    ll ans = INF;
    for (auto [_, d] : mpAns) ans = min(ans, d);
    // for (auto [_, d] : mp) cerr << _ <<  ": " << d << '\n';
    // cerr << mpAns.size() << '\n';
    return ans;
}

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