Submission #1082429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082429		PanosPask	Towns (IOI15_towns)	C++14	35 / 100	13 ms	600 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 d2[a] + d2[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);

    bool balanced;
    vector<int> special;
    for (int i = 0; i < N; i++) {
        int res = distFromS(i);
        if (res >= hubdist) {
            special.push_back(i);
        }
    }
    balanced = (N - special.size()) <= N / 2;

    vector<int> nxt;
    vector<int> dead;
    vector<int> cnt(N, 1);
    while (special.size() > 1) {
        for (int i = 1; i < special.size(); i += 2) {
            if (!differentBranch(special[i - 1], special[i])) {
                nxt.push_back(special[i]);
                cnt[special[i]] += cnt[special[i - 1]];
            }
            else {
                dead.push_back(special[i]);
                dead.push_back(special[i - 1]);
            }
        }
        if (special.size() % 2) {
            dead.push_back(special.back());
        }

        swap(nxt, special);
        nxt.clear();
    }

    if (special.size() != 0) {
        for (auto d : dead) {
            if (!differentBranch(special.front(), d)) {
                cnt[special.front()] += cnt[d];
            }
        }

        balanced = balanced && cnt[special.front()] <= N / 2;
    }

    return balanced ? opt : -opt;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:160:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |     balanced = (N - special.size()) <= N / 2;
      |                ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
towns.cpp:166:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |         for (int i = 1; i < special.size(); i += 2) {
      |                         ~~^~~~~~~~~~~~~~~~
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: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39