Submission #1270765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270765		Faggi	도시들 (IOI15_towns)	C++20	13 / 100	9 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, r = max(d1, d2), d, j, ac, num;
    vector<set<ll>> un(N);
    for (i = 0; i < N; i++)
        un[i].insert(i);

    vector<ll> v;
    v.pb(0);
    for (i = 1; i < N; i++)
    {
        if (sz(v) == 0)
            v.pb(i);
        else
        {
            d = max(dis[x][i] - d1, dis[y][i] - d2);
            j = v.back();
            ac = max(dis[x][j] - d1, dis[y][j] - d2);
            if(dis[i][j]==-1)
                dis[i][j]=dis[j][i]=getDistance(i,j);
            if (dis[i][j] - d != ac)
            {
                v.pop_back();
                i--;
            }
            else
                v.pb(i);
        }
    }
    if (sz(v) == 0)
        return N / 2;
    num = v.back();
    v.resize(0);
    v.pb(num);
    d = max(dis[x][num] - d1, dis[y][num] - d2);
    for (i = 0; i < N; i++)
    {
        if (i == num)
            continue;
        if(dis[i][j]==-1)
            dis[i][j]=dis[j][i]=getDistance(i,j);
        ac = max(dis[x][i] - d1, dis[y][i] - d2);
        if (dis[i][j] - d == ac)
            v.pb(i);
    }
    return sz(v);
}
int hubDistance(int N, int sub)
{
    vector<vector<ll>> dis(N, vector<ll>(N, -1));
    vector<vector<ll>> v;
    ll i, j, k, d, R = LLONG_MAX, r;
    for(i=0; i<N; i++)
        dis[i][i]=0;
    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: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39