Submission #1082234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082234		PanosPask	도시들 (IOI15_towns)	C++14	25 / 100	12 ms	1116 KiB

towns

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

using namespace std;

int N;
int diameter = 0;
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;
}

// Projecting to the diameter counting from n1
int projection(int u, vector<int>& d)
{
    int pathlen = (d1[u] + d2[u] - diameter) / 2;

    return d[u] - pathlen;
}

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);

    diameter = d1[n2];

    int ans = 1e9 + 7;
    for (int i = 0; i < N; i++) {
        int res = max(projection(i, d1), projection(i, d2));

        ans = min(ans, res);
    }

    return ans;
}

Compilation message (stderr)

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