Submission #727957

#	Time	Username	Problem	Language	Result	Execution time	Memory
727957		vjudge1	Towns (IOI15_towns)	C++11	38 / 100	17 ms	980 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, c = -1;
        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)});
                if (res > ans) res = ans, c = i;
        }

        if (sub < 3) return res / 2;

        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 (max(dia - dist_hub, dist_hub) == res) {
                        for (int j = 0; j < N; j++) cnt[j] = 0;
                        cnt[a] = cnt[b] = 1;
                        vector<int> notab;
                        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 {
                                        notab.emplace_back(j);
                                }
                        }
                        for (int j = 0; j < notab.size(); j++) g[notab[j]] = notab[j];
                        for (int j = 0; j < notab.size(); j++) {
                                cnt[g[notab[j]]]++;
                                if (g[notab[j]] != notab[j]) continue;
                                for (int k = j + 1; k < notab.size(); k++) {
                                        if (g[notab[k]] != notab[k]) continue;
                                        int x = notab[j], y = notab[k];
                                        bool same_group = (dist(a, x) + dist(a, y) - dist(x, y)) > dist_hub;
                                        if (same_group) g[y] = x;
                                }
                        }
                        bool ok = 1;
                        for (int j = 0; j < N; j++) {
                                if (cnt[j] > N / 2) ok = 0;
                        }
                        if (ok) return res / 2;
                }
        }
        return -res / 2;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:55:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                         for (int j = 0; j < notab.size(); j++) g[notab[j]] = notab[j];
      |                                         ~~^~~~~~~~~~~~~~
towns.cpp:56:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                         for (int j = 0; j < notab.size(); j++) {
      |                                         ~~^~~~~~~~~~~~~~
towns.cpp:59:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                                 for (int k = j + 1; k < notab.size(); k++) {
      |                                                     ~~^~~~~~~~~~~~~~
towns.cpp:27:24: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   27 |         int res = 1e9, c = -1;
      |                        ^

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