Submission #831148

#	Time	Username	Problem	Language	Result	Execution time	Memory
831148		skittles1412	Towns (IOI15_towns)	C++17	25 / 100	13 ms	1088 KiB

towns

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

int getDistance(int i, int j);

struct G {
    map<pair<int, int>, int> cache;

    int query(int u, int v) {
        if (u > v) {
            swap(u, v);
        }
        auto [it, inserted] = cache.insert({{u, v}, -1});
        if (!inserted) {
            return it->second;
        }
        return it->second = getDistance(u, v);
    }
} G;

int hubDistance(int n, int tc_id) {
    G = {};

    auto farthest = [&](int u) -> int {
        pair<int, int> ans {-1, 0};
        for (int i = 0; i < n; i++) {
            ans = max(ans, {G.query(u, i), i});
        }
        return ans.second;
    };

    int u1 = farthest(0), u2 = farthest(u1);

    int u_hori[n], u_down[n];
    for (int i = 0; i < n; i++) {
        int d1 = G.query(u1, i), d2 = G.query(u2, i);

        u_down[i] = (d1 + d2 - G.query(u1, u2)) / 2;
        u_hori[i] = d1 - u_down[i];
    }

    int ans = 1e9;

    for (int i = 0; i < n; i++) {
        ans = min(ans, max(u_hori[i], G.query(u1, u2) - u_hori[i]));
    }

    return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:28: warning: unused parameter 'tc_id' [-Wunused-parameter]
   44 | int hubDistance(int n, int tc_id) {
      |                        ~~~~^~~~~

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