Submission #1270327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270327		Faggi	Towns (IOI15_towns)	C++20	26 / 100	437 ms	13536 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;
    vector<set<ll>>un(N);
    for(i=0; i<N; i++)
        un[i].insert(i);
    for(i=0; i<N; i++)
    {
        d=max(dis[x][i]-d1,dis[y][i]-d2);
        for(j=0; j<N; j++)
        {
            if(j==i)
                continue;
            ac=max(dis[x][j]-d1,dis[y][j]-d2);
            if(dis[i][j]-d!=ac)
            {
                for(auto k:un[i])
                    un[j].insert(k);
                for(auto k:un[j])
                    un[i].insert(k);
            }
        }
    }
    ll ans=0;
    for(i=0; i<N; 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;
    for(i=0; i<N; i++)
    {
        for(j=i+1; j<N; j++)
        {
            dis[j][i]=dis[i][j]=getDistance(i,j);
        }
    }
    for(i=0; i<N; i++)
    {
        for(j=i+1; j<N; j++)
        {
            for(k=j+1; k<N; k++)
            {
                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});
                }
            }
        }
    }
    ll 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: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39