Submission #1271048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271048		Faggi	Towns (IOI15_towns)	C++20	35 / 100	17 ms	584 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;
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int getRandomInt(int l, int r) { 
    std::uniform_int_distribution<int> dist(l, r); 
    return dist(rng); 
}

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, a, b, ra;

    vector<vector<ll>> v, nv, die;
    for (i = 0; i < N; i++)
        v.pb({i});
    while (sz(v) > 1)
    {
        if (sz(v) % 2 != 0)
        {
            die.pb(v.back());
            v.pop_back();
        }
        while(sz(v)>1)
        {
            a=getRandomInt(0, sz(v) - 1);
            d = max(dis[x][a] - d1, dis[y][a] - d2);
            vector<ll>ins=v[a];
            v.erase(v.begin()+a);
            b=getRandomInt(0, sz(v) - 1);
            ac = max(dis[x][b] - d1, dis[y][b] - d2);
            if (dis[a][b] == -1)
                dis[a][b] = dis[b][a] = getDistance(a, b);
            if (dis[x][a]+dis[x][b]-dis[a][b]>2*r)
            {
                for(auto k:v[b])
                    ins.pb(k);
                nv.pb(ins);
            }
            else
            {
                die.pb(ins);
                die.pb(v[b]);
            }
            v.erase(v.begin()+b);
        }
        v = nv;
        nv.resize(0);
    }
    if (sz(v) == 0)
        return N / 2;
    a = v[0][0];
    d = max(dis[x][a] - d1, dis[y][a] - d2);
    for (i = 0; i < sz(die); i++)
    {
        b = die[i][0];
        ac = max(dis[x][b] - d1, dis[y][b] - d2);
        if (dis[a][b] == -1)
            dis[a][b] = dis[b][a] = getDistance(a, b);
        if (dis[x][a]+dis[x][b]-dis[a][b]>2*r)
            for (auto k : die[i])
                v[0].pb(k);
    }
    return sz(v[0]);
}
pair<ll,ll>nods(ll x, ll d1, ll y, ll d2, vector<vector<ll>> &dis, ll N)
{
    pair<ll,ll>p= {1,1};
    ll i, ac;
    for(i=0; i<N; i++)
    {
        if(i==x||i==y)
            continue;
        ac = max(dis[x][i] - d1, dis[y][i] - d2);
        if(dis[x][i]-d1!=ac)
            p.fr++;
        else if(dis[y][i]-d2!=ac)
            p.se++;
    }
    return p;
}
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);
    mj=0;

    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});
        }
    }
    pair<ll,ll>p=nods(v[0][0], v[0][1], v[0][2], v[0][3], dis, N);
    if(p.fr>N/2)
        mi=N;
    else if(p.se>N/2)
        mi=N;
    else if(p.se==N/2||p.fr==N/2)
        mi=N/2;
    else if(p.se+p.fr>=N/2)
        mi=N/2;
    else
        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;
        p=nods(v[i][0], v[i][1], v[i][2], v[i][3], dis, N);
        if(p.fr>N/2)
            mi=min(mi,1ll*N);
        else if(p.se>N/2)
            mi=min(mi,1ll*N);
        else if(p.se==N/2||p.fr==N/2)
            mi=min(mi,1ll*N/2);
        else if(p.se+p.fr>=N/2)
            mi=min(mi,1ll*N/2);
        else
            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