Submission #1082235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082235		PanosPask	Towns (IOI15_towns)	C++14	35 / 100	14 ms	468 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 n_i
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;
    bool balanced = false;
    for (int i = 0; i < N; i++) {
        int res = max(projection(i, d1), projection(i, d2));

        if (res <= ans) {
            if (res < ans) {
                balanced = false;
            }
            ans = res;

            int cmp = projection(i, d1);
            int a = 0, b = 0, c = 0;

            for (int j = 0; j < N; j++) {
                int p = projection(j, d1);

                if (p < cmp) {
                    a++;
                }
                else if (p > cmp) {
                    b++;
                }
                else {
                    c++;
                }
            }

            balanced = balanced || (max(max(a, b), c) <= N / 2);
        }
    }

    if (balanced) {
        return ans;
    }
    else {
        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: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39