Submission #1082423

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

towns

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

using namespace std;

int N;
int diameter = 0;
int hubdist = 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) - diameter) / 2;
    }

    return distance(s, node) - commonpath;
}

bool differentBranch(int a, int b)
{
    return distFromS(a) + distFromS(b) - getDistance(a, b) == 2 * hubdist;
}

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

    int opt = min(ans2, diameter - ans1);
    if (ans2 != opt) {
        u2 = -1;
    }
    if (diameter - ans1 != opt) {
        u1 = -1;
    }

    if (u1 != -1 && u2 != -1) {
        // Find the best
        int bef = 0, at = 0, aft = 0;

        for (int i = 0; i < N; i++) {
            int res = distFromS(i);
            if (res < ans1) {
                bef++;
            }
            else if (res == ans1) {
                at++;
            }
            else {
                aft++;
            }
        }

        if (at + bef <= N / 2) {
            u1 = -1;
        }
        else {
            u2 = -1;
        }
    }

    // The hub is the projection of small town i into the diameter
    int hub = u1 != -1 ? u1 : u2;
    hubdist = distFromS(hub);

    return opt;
}

Compilation message (stderr)

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