Submission #1095476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095476		MMihalev	Towns (IOI15_towns)	C++14	25 / 100	12 ms	1224 KiB

towns

#include "towns.h"
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAX_N=2e2+2;
int diam;
int tov[MAX_N];
int tou[MAX_N];
int to0[MAX_N];
int n;

int hubDistance(int N, int sub)
{
    n=N;

    int u=0;
    int far=0,v;
    for(int i=1;i<n;i++)
    {
        int cur=getDistance(u,i);
        to0[i]=cur;
        if(cur>far)
        {
            far=cur;
            v=i;
        }
    }//0->v

    diam=0;
    for(int i=0;i<n;i++)
    {
        if(i==v)continue;
        int cur;
        if(i==0)cur=to0[v];
        else cur=getDistance(i,v);

        tov[i]=cur;

        if(cur>diam)
        {
            diam=cur;
            u=i;
        }
    }//v->u

    for(int i=0;i<n;i++)
    {
        if(i==u)continue;
        if(i==0)tou[i]=to0[u];
        if(i==v)tou[i]=tov[u];
        tou[i]=getDistance(u,i);
    }//u->all


    int cntneg=0,cntpos=0;
    int mindif=1e9;
    for(int i=0;i<n;i++)
    {
        if(i==u or i==v)continue;

        int x=tou[i];
        int y=tov[i];
        int com=((x+y)-diam)/2;

        x-=com;
        y-=com;

        int res=x-y;

        if(res<0)cntneg++;
        else if(res>0)cntpos++;

        mindif=min(mindif,abs(res));
    }

    int R=(diam-mindif)/2+mindif;

	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:13:28: warning: unused parameter 'sub' [-Wunused-parameter]
   13 | int hubDistance(int N, int sub)
      |                        ~~~~^~~
towns.cpp:36:29: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |         else cur=getDistance(i,v);
      |                  ~~~~~~~~~~~^~~~~

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