Submission #1141477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141477		efishel	Towns (IOI15_towns)	C++20	0 / 100	1096 ms	25848 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;

    DSU (ll n): par(n) { 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) {
        par[find(u)] = par[find(v)];
    }
};

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 = 1; 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++ });
            }
        }
    }
    auto fsame = [&](Info a, Info b) {
        if (a.u1 == b.u1) return a.dis1 == b.dis1;
        if (a.u1 == b.u2) return a.dis1 == b.dis2;
        if (a.u1 == b.u3) return a.dis1 == b.dis3;
        if (a.u2 == b.u1) return a.dis2 == b.dis1;
        if (a.u2 == b.u2) return a.dis2 == b.dis2;
        if (a.u2 == b.u3) return a.dis2 == b.dis3;
        if (a.u3 == b.u1) return a.dis3 == b.dis1;
        if (a.u3 == b.u2) return a.dis3 == b.dis2;
        if (a.u3 == b.u3) return a.dis3 == b.dis3;
        return false;
    };
    DSU dsu(id);
    map <ii, map <ii, ll> > mp;
    for (auto [u1, u2, u3, dis1, dis2, dis3, id] : ve) {
        if (mp.count({ u1, u2 }) && mp[{ u1, u2 }].count({ dis1, dis2 })) dsu.join(id, mp[{ u1, u2 }][{ dis1, dis2 }]);
        if (mp.count({ u1, u3 }) && mp[{ u1, u3 }].count({ dis1, dis3 })) dsu.join(id, mp[{ u1, u3 }][{ dis1, dis3 }]);
        if (mp.count({ u2, u3 }) && mp[{ u2, u3 }].count({ dis2, dis3 })) dsu.join(id, mp[{ u2, u3 }][{ dis2, dis3 }]);
        mp[{ u1, u2 }][{ dis1, dis2 }] = id;
        mp[{ u1, u3 }][{ dis1, dis3 }] = id;
        mp[{ u2, u3 }][{ dis2, dis3 }] = id;
        // for (Info b : ve) {
        //     if (fsame(a, b)) dsu.join(a.id, b.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 });
    }
    ll ans = INF;
    for (auto [_, d] : mpAns) ans = min(ans, d);
    // for (auto [_, d] : mp) cerr << _ <<  ": " << d << '\n';
    // cerr << mp.size() << '\n';
    return ans;
    // vll disToPar(n, INF);
    // for (ll i = 1; i < n; i++) {
    //     for (ll j = i+1; j < n; j++) {
    //         ll x = dis[i][j], y = dis[i][0], z = dis[j][0];
    //         ll disI = (z-x-y)/-2, disJ = (y-x-z)/-2;
    //         disToPar[i] = min(disToPar[i], disI);
    //         disToPar[j] = min(disToPar[j], disJ);
    //     }
    // }
    // DSU dsu(n);
    // vll remDis(n, 0);
    // for (ll i = 1; i < n; i++) {
    //     for (ll j = i+1; j < n; j++) {
    //         ll x = dis[i][j], y = dis[i][0], z = dis[j][0];
    //         ll disI = (z-x-y)/-2, disJ = (y-x-z)/-2;
    //         if (disI != disToPar[i] || disJ != disToPar[j]) continue;
    //         dsu.join(i, j);
    //     }
    // }
    return 0;
}

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