Submission #494881

#	Time	Username	Problem	Language	Result	Execution time	Memory
494881		thecodingwizard	Towns (IOI15_towns)	C++11	26 / 100	120 ms	1196 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

#define ii pair<int, int>
#define mp make_pair
#define inf 1e9;
#define f first
#define s second

map<ii, int> cached;
int getD(int a, int b) {
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (cached.count(mp(a, b))) return cached[mp(a, b)];
    return cached[mp(a, b)] = getDistance(a, b);
}

int hubDistance(int N, int sub) {
    cached.clear();

    int u, v;

    int maxDist = -1;
    for (int i = 0; i < N; i++) {
        if (getD(0, i) > maxDist) {
            maxDist = getD(0, i);
            u = i;
        }
    }

    maxDist = -1;
    for (int i = 0; i < N; i++) {
        if (getD(u, i) > maxDist) {
            maxDist = getD(u, i);
            v = i;
        }
    }

    int radius = inf;
    int d1 = -1, d2 = -1;
    for (int i = 0; i < N; i++) {
        int distFromHubToU = (getD(u, i) + getD(u, 0) - getD(i, 0))/2;
        int distFromHubToV = getD(u, v) - distFromHubToU;
        if (max(distFromHubToU, distFromHubToV) < radius) {
            radius = max(distFromHubToU, distFromHubToV);
            d1 = distFromHubToU;
            d2 = -1;
        } else if (max(distFromHubToU, distFromHubToV) == radius) {
            if (distFromHubToU != d1) {
                d2 = distFromHubToU;
            }
        }
    }
    if (d2 != -1 && d1 > d2) swap(d1, d2);

    bool balanced = true;
    map<int, int> frequency;
    for (int i = 0; i < N; i++) {
        int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2;
        frequency[distFromU]++;
    }

    int ct1 = 0;
    int ct2 = 0;
    for (auto x : frequency) {
        if (x.f <= d1) ct1 += x.s;
        if (x.f <= d2) ct2 += x.s;
    }
    // cout << ct1 << " " << ct2 << " "<< d1 << " "<< d2 << endl;
    bool isHub2 = false;
    if (ct1 - frequency[d1] > N/2) balanced = false;
    if (ct1 < N/2) {
        if (d2 != -1) {
            if (ct2 - frequency[d2] <= N/2 && ct2 >= N/2) {
                isHub2 = true;
            }
            else balanced = false;
        } else {
            balanced = false;
        }
    }
    if (balanced) {
        int distToHub = -1;
        if (isHub2) {
            distToHub = d2;
        } else {
            distToHub = d1;
        }
        for (int i = 0; i < N; i++) {
            int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2;
            if (distFromU != distToHub) continue;
            int sz = 1;
            for (int j = 0; j < N; j++) {
                int distFromU = (getD(u, j) + getD(u, 0) - getD(0, j))/2;
                if (distFromU != distToHub) continue;
                if (getD(i, u) + getD(j, u) - getD(i, j) != distToHub*2) {
                    sz++;
                }
            }
            if (sz > N/2) balanced = false;
        }
    }

    return (balanced ? 1 : -1) * radius;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:96:21: warning: declaration of 'distFromU' shadows a previous local [-Wshadow]
   96 |                 int distFromU = (getD(u, j) + getD(u, 0) - getD(0, j))/2;
      |                     ^~~~~~~~~
towns.cpp:92:17: note: shadowed declaration is here
   92 |             int distFromU = (getD(u, i) + getD(u, 0) - getD(0, i))/2;
      |                 ^~~~~~~~~
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
   20 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp:98:38: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |                 if (getD(i, u) + getD(j, u) - getD(i, j) != distToHub*2) {
      |                                  ~~~~^~~~~~
towns.cpp:45:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |         int distFromHubToV = getD(u, v) - distFromHubToU;
      |                              ~~~~^~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39