Submission #1270349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270349		Faggi	Towns (IOI15_towns)	C++20	35 / 100	10 ms	580 KiB

towns

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
int getDistance(int i, int j);
ll calc(ll x, ll d1, ll y, ll d2, vector<vector<ll>> &dis, ll N)
{
    ll i, r = max(d1, d2), d;
    for (i = 0; i < N; i++)
    {
        if (x == i || y == i)
            continue;
        d = max(dis[x][i] - d1, dis[y][i] - d2);
        r = max(d, r);
    }
    return r;
}
ll tam(ll x, ll d1, ll y, ll d2, vector<vector<ll>> &dis, ll N)
{
    ll i, d, j, ac;
    vector<set<ll>> un(3);
    un[0].insert(x);
    un[1].insert(y);
    for (i = 0; i < N; i++)
    {
        d = max(dis[x][i] - d1, dis[y][i] - d2);
        if(d!=dis[x][i] - d1)
            un[0].insert(i);
        else if(d!=dis[y][i] - d2)
            un[1].insert(i);
        else
            un[2].insert(i);
    }
    ll ans = 0;
    for (i = 0; i < sz(un); i++)
        ans = max(ans, 1ll * sz(un[i]));
    return ans;
}
int hubDistance(int N, int sub)
{
    vector<vector<ll>> dis(N, vector<ll>(N, 0));
    vector<vector<ll>> v;
    ll i, j, k, d, R = LLONG_MAX, r;
    vector<bool> vis(N, 0);
    vis[0] = 1;
    for (i = 1; i < N; i++)
        dis[0][i] = dis[i][0] = getDistance(0, i);
    ll ma = 0, mi = 0, mj = 0;
    for (i = 0; i < N; i++)
    {
        if (ma < dis[i][0])
        {
            ma = dis[i][0];
            mi = i;
        }
    }
    vis[mi] = 1;
    for (i = 0; i < N; i++)
        if (mi != i)
            dis[mi][i] = dis[i][mi] = getDistance(mi, i);
    ma = 0;
    for (i = 0; i < N; i++)
    {
        if (ma < dis[i][mi])
        {
            ma = dis[i][mi];
            mj = i;
        }
    }
    if (vis[mj] == 0)
    {
        for (i = 0; i < N; i++)
            if (mj != i)
                dis[mj][i] = dis[i][mj] = getDistance(mj, i);
    }

    i = mi;
    j = mj;
    for (k = 0; k < N; k++)
    {
        if(k==j||k==i)
            continue;
        d = (dis[i][j] + dis[i][k] - dis[j][k]) / 2;
        r = calc(i, d, j, dis[i][j] - d, dis, N);
        if (R > r)
        {
            R = r;
            v.resize(0);
            v.pb({i, d, j, dis[i][j] - d});
        }
        else if (R == r)
        {
            v.pb({i, d, j, dis[i][j] - d});
        }
    }
    mi = tam(v[0][0], v[0][1], v[0][2], v[0][3], dis, N);

    for (i = 1; i < sz(v); i++)
    {
        d = max(dis[v[i][0]][v[0][0]] - v[i][1], dis[v[i][2]][v[0][0]] - v[i][3]);
        if (d == v[0][1])
            continue;
        mi = min(tam(v[i][0], v[i][1], v[i][2], v[i][3], dis, N), mi);
        break;
    }
    if (mi > N / 2)
        R = -R;
    return R;
}

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