Submission #1082233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082233		PanosPask	Towns (IOI15_towns)	C++14	25 / 100	14 ms	1116 KiB

towns

#include "towns.h"
#include <vector>

using namespace std;

int N;
vector<int> d1;
vector<int> d2;

void findAll(int u, vector<int>& d)
{
    d.resize(N);

    d[u] = 0;
    for (int i = 0; i < N; i++) {
        if (i != u) {
            d[i] = getDistance(u, i);
        }
    }
}

int getPos(vector<int>& d)
{
    int m_i = -1;
    int m_v = -1;

    for (int i = 0; i < N; i++) {
        if (d[i] > m_v) {
            m_i = i;
            m_v = d[i];
        }
    }

    return m_i;
}

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

    findAll(0, d1);
    int n1 = getPos(d1);
    findAll(n1, d1);
    int n2 = getPos(d1);
    findAll(n2, d2);

    int diameter = d1[n2];

    int ans = 1e9 + 7;
    for (int i = 0; i < N; i++) {
        int pathlen = (d1[i] + d2[i] - diameter) / 2;
        
        ans = min(ans, max(d1[i], d2[i]) - pathlen);
    }

    return ans;
}

Compilation message (stderr)

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