Submission #787807

#	Time	Username	Problem	Language	Result	Execution time	Memory
787807		vnm06	Towns (IOI15_towns)	C++14	25 / 100	13 ms	956 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;

int st[150][150];

int pitaj(int i, int j)
{
    if(st[i][j]!=-1) return st[i][j];
    st[i][j]=getDistance(i, j);
    st[j][i]=st[i][j];
    return st[i][j];
}

int hubDistance(int N, int sub)
{
    int n=N;
    memset(st, -1, sizeof(st));
    for(int i=0; i<n; i++) st[i][i]=0;
    int v1=0;
    for(int i=1; i<n; i++)
    {
        if(pitaj(0, i)>pitaj(0, v1)) v1=i;
    }
    int v2=0;
    for(int i=0; i<n; i++)
    {
        if(pitaj(v1, i)>pitaj(v1, v2)) v2=i;
    }
    int R=1e9;
    for(int i=0; i<n; i++)
    {
        if(i==v1 || i==v2) continue;
        int t1=pitaj(i, v1);
        int t2=pitaj(i, v2);
        int t3=pitaj(v1, v2);
        int r1=(t1+t3-t2)/2, r2=(t2+t3-t1)/2;
        if(max(r1, r2)<R) R=max(r1, r2);
    }
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:15:28: warning: unused parameter 'sub' [-Wunused-parameter]
   15 | 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