Submission #1141501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141501		efishel	도시들 (IOI15_towns)	C++20	13 / 100	293 ms	8944 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>;
using vi = vector <int>;

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

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

struct Info {
    int p1, p2, p3, id;
};

struct DSU {
    vi par;
    vi sz;

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

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

    void join (int u, int 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++ });
                ve.push_back({ dis1<<8|u1, dis2<<8|u2, dis3<<8|u3, id++ });
            }
        }
    }
    // map <pair <ii, ii>, ll> mp;
    unordered_map <ll, ll> mp;
    DSU dsu(id);
    // for (auto [u1, u2, u3, dis1, dis2, dis3, id] : ve) {
    for (auto [p1, p2, p3, id] : ve) {
        if (!mp.count(ll(p1)<<32|ll(p2))) mp[ll(p1)<<32|ll(p2)] = id;
        if (!mp.count(ll(p1)<<32|ll(p3))) mp[ll(p1)<<32|ll(p3)] = id;
        if (!mp.count(ll(p2)<<32|ll(p3))) mp[ll(p2)<<32|ll(p3)] = id;
        ll a = mp[ll(p1)<<32|ll(p2)];
        ll b = mp[ll(p1)<<32|ll(p3)];
        ll c = mp[ll(p2)<<32|ll(p3)];
        dsu.join(a, id);
        dsu.join(b, id);
        dsu.join(c, id);
    }
    map <ll, int> mpAns;
    for (auto [p1, p2, p3, id] : ve) {
        mpAns[dsu.find(id)] = max({ mpAns[dsu.find(id)], p1>>8, p2>>8, p3>>8 });
    }
    // 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';
    // }
    int ans = INF;
    for (auto [_, d] : mpAns) ans = min(ans, d);
    // for (auto [_, d] : mp) cerr << _ <<  ": " << d << '\n';
    // cerr << mpAns.size() << '\n';
    return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:66:39: warning: narrowing conversion of '((dis1 << 8) | u1)' from 'std::tuple_element<0, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |                 ve.push_back({ dis1<<8|u1, dis2<<8|u2, dis3<<8|u3, id++ });
      |                                ~~~~~~~^~~
towns.cpp:66:51: warning: narrowing conversion of '((dis2 << 8) | u2)' from 'std::tuple_element<1, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |                 ve.push_back({ dis1<<8|u1, dis2<<8|u2, dis3<<8|u3, id++ });
      |                                            ~~~~~~~^~~
towns.cpp:66:63: warning: narrowing conversion of '((dis3 << 8) | u3)' from 'std::tuple_element<2, std::array<long long int, 3> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |                 ve.push_back({ dis1<<8|u1, dis2<<8|u2, dis3<<8|u3, id++ });
      |                                                        ~~~~~~~^~~
towns.cpp:66:70: warning: narrowing conversion of '(id ++)' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   66 |                 ve.push_back({ dis1<<8|u1, dis2<<8|u2, dis3<<8|u3, id++ });
      |                                                                    ~~^~

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