Submission #778287

#	Time	Username	Problem	Language	Result	Execution time	Memory
778287		boris_mihov	Towns (IOI15_towns)	C++17	25 / 100	16 ms	1100 KiB

towns

#include "towns.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int query(int u, int v)
{
    return getDistance(u - 1, v - 1);
}

int distA[MAXN];
int distB[MAXN];
int distC[MAXN];
int hubDistance(int n, int sub) 
{
    int max = 0;
    int dist = 0;
    for (int i = 2 ; i <= n ; ++i)
    {
        distA[i] = query(1, i);
        if (distA[i] > dist)
        {
            max = i;
            dist = distA[i];
        }
    }

    dist = 0;
    int end = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        distB[i] = query(max, i);
        if (distB[i] > dist)
        {
            end = i;
            dist = distB[i];
        }
    }

    int diff = INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        distC[i] = query(i, end);
        diff = std::min(diff, abs(distB[i] - distC[i]));
    }

    return (distB[end] + diff) / 2;
}

Compilation message (stderr)

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