Submission #728004

#	Time	Username	Problem	Language	Result	Execution time	Memory
728004		vjudge1	Towns (IOI15_towns)	C++11	39 / 100	19 ms	908 KiB

towns

#include "towns.h"

#include <bits/stdc++.h>
using namespace std;

int f[110][110];
int g[110];
int cnt[110];

inline int dist(int i, int j) {
        if (f[i][j] == -1) return f[i][j] = f[j][i] = getDistance(i, j);
        return f[i][j];
}

int hubDistance(int N, int sub) {
        int a = 0, b = 0, dia = 0;
        for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) f[i][j] = i == j ? 0 : -1;
        }
        for (int i = 0; i < N; i++) {
                if (dia < dist(a, i)) dia = dist(a, i), b = i;
        }
        for (int i = 0; i < N; i++) {
                if (dia < dist(i, b)) dia = dist(i, b), a = i;
        }
        dia *= 2;
        int res = 1e9;
        for (int i = 0; i < N; i++) {
                int ans = max({dist(a, b) + dist(b, i) - dist(a, i),
                               dist(a, b) + dist(a, i) - dist(b, i),
                               dist(a, i) + dist(b, i) - dist(a, b)});
                res = min(res, ans);
        }

        assert(res % 2 == 0);
        res /= 2;

        map<int, int> done;
        for (int i = 0; i < N; i++) {
                if (i == a || i == b) continue;
                int dist_hub = dist(a, b) + dist(a, i) - dist(i, b);
                if (done[dist_hub] == 1) continue;
                done[dist_hub] = 1;
                if (max(dia - dist_hub, dist_hub) == res * 2) {
                        for (int j = 0; j < N; j++) cnt[j] = 0;
                        cnt[a] = cnt[b] = 1;
                        vector<vector<int>> alive, dead;
                        vector<int> majority;
                        for (int j = 0; j < N; j++) {
                                if (j == a || j == b) continue;
                                int dist_j = dist(a, b) + dist(a, j) - dist(j, b);
                                if (dist_j < dist_hub) {
                                        cnt[a]++;
                                } else if (dist_j > dist_hub) {
                                        cnt[b]++;
                                } else {
                                        alive.push_back({j});
                                }
                        }
                        if (cnt[a] > N / 2) continue;
                        if (cnt[b] > N / 2) continue;
                        if (alive.size() <= N / 2) return res;
                        while (!alive.empty()) {
                                vector<vector<int>> new_alive;
                                for (int j = 0; j < alive.size(); j += 2) {
                                        if (j + 1 == alive.size()) {
                                                if (!majority.empty()) dead.push_back(majority);
                                                majority = alive[j];
                                        } else {
                                                if (dist(a, alive[j][0]) + dist(a, alive[j + 1][0]) - dist(alive[j][0], alive[j + 1][0]) > dist_hub) {
                                                        alive[j].insert(alive[j].end(), alive[j + 1].begin(), alive[j + 1].end());
                                                        new_alive.push_back(alive[j]);
                                                } else {
                                                        dead.push_back(alive[j]);
                                                        dead.push_back(alive[j + 1]);
                                                }
                                        }
                                }
                                alive = new_alive;
                        }
                        int sus = (int)majority.size();
                        if (sus == 0) return res;
                        for (auto ded : dead) {
                                if (dist(a, ded[0]) + dist(a, majority[0]) - dist(ded[0], majority[0]) > dist_hub) sus += (int)ded.size();
                        }
                        if (sus <= N / 2) return res;
                }
        }
        return -res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:62:42: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |                         if (alive.size() <= N / 2) return res;
      |                             ~~~~~~~~~~~~~^~~~~~~~
towns.cpp:65:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                                 for (int j = 0; j < alive.size(); j += 2) {
      |                                                 ~~^~~~~~~~~~~~~~
towns.cpp:66:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                                         if (j + 1 == alive.size()) {
      |                                             ~~~~~~^~~~~~~~~~~~~~~
towns.cpp:15:28: warning: unused parameter 'sub' [-Wunused-parameter]
   15 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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