Submission #705828

#	Time	Username	Problem	Language	Result	Execution time	Memory
705828		bin9638	Towns (IOI15_towns)	C++17	25 / 100	14 ms	968 KiB

towns

#include <bits/stdc++.h>

#ifndef SKY
#include<towns.h>
#endif

using namespace std;

#define ll long long
#define fs first
#define sc second
#define N 210
#define pb push_back
#define ii pair<ll,ll>

int dis[N][N],c[N][N];

#ifdef SKY
int getDistance(int i, int j)
{
    return dis[i][j];
}
#endif // SKY


int hubDistance(int n, int sub)
{
    for(int i=1;i<n;i++)
        c[0][i]=c[i][0]=getDistance(0,i);
    int S=1;
    for(int i=1;i<n;i++)
        if(c[0][i]>c[0][S])
            S=i;
    // da tinh 0
    for(int i=1;i<n;i++)
        if(i!=S)
            c[S][i]=c[i][S]=getDistance(S,i);
    int T=0;
    for(int i=0;i<n;i++)
        if(c[S][i]>c[S][T])
            T=i;
    //cout<<S<<" "<<T<<endl;
    int L=(c[S][T]+c[0][S]+c[0][T])/2-c[0][T],
        R=(c[S][T]+c[0][S]+c[0][T])/2-c[0][S],
        K=(c[S][T]+c[0][S]+c[0][T])/2-c[S][T];
    int res=max(L,R);
   // cout<<L<<" "<<R<<" "<<K<<endl;
    for(int i=1;i<n;i++)
        if(!(c[S][i]-c[0][i]>=L-K))
        //if(i==0)
        {

            int length=(c[S][i]+c[0][i]+c[0][S])/2-c[0][i];
            //cout<<length<<endl;
           // cout<<i<<" "<<length<<" "<<dis[S][T]-length<<endl;
            res=min(res,max(length,c[S][T]-length));
        }
    return res;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    int n;
    int q;
    cin>>q;
    while(q--)
    {
        int n,sub;
        cin>>sub>>n;
        //cout<<n<<endl;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>dis[i][j];
        cout<<hubDistance(n, sub)<<endl;
    }
    return 0;
}
#endif // SKY

Compilation message (stderr)

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

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