Submission #1082418

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

towns

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

using namespace std;

int N;
int diameter = 0;

int v, s, t;

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 distance(int i, int j)
{
    if (i == v) {
        return d1[j];
    }
    else if (j == v) {
        return d1[i];
    }
    else if (i == s) {
        return d2[j];
    }
    else if (j == s) {
        return d2[i];
    }

    return getDistance(i, j);
}

int distFromS(int node)
{
    int commonpath = 0;

    if (node != v) {
        commonpath = (distance(node, v) + distance(node, s) - distance(v, s)) / 2;
    }
    else {
        commonpath = (distance(node, t) + distance(node, s) - distance(t, s)) / 2;
    }

    return distance(s, node) - commonpath;
}

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

    v = 0;
    findAll(v, d1);
    s = getPos(d1);
    findAll(s, d2);
    t = getPos(d2);


    diameter = d2[t];

    int ans1 = -1;
    int ans2 = 1e6 + 1;

    int u1 = -1;
    int u2 = -1;

    for (int i = 0; i < N; i++) {
        int res = distFromS(i);

        if (2 * res < diameter) {
            if (ans1 < res) {
                ans1 = res;
                u1 = i;
            }
        }
        else {
            if (ans2 > res) {
                ans2 = res;
                u2 = i;
            }
        }
    }

    return min(ans2, diameter - ans1);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:89:9: warning: variable 'u1' set but not used [-Wunused-but-set-variable]
   89 |     int u1 = -1;
      |         ^~
towns.cpp:90:9: warning: variable 'u2' set but not used [-Wunused-but-set-variable]
   90 |     int u2 = -1;
      |         ^~
towns.cpp:73:28: warning: unused parameter 'sub' [-Wunused-parameter]
   73 | 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