Submission #727889

#	Time	Username	Problem	Language	Result	Execution time	Memory
727889		vjudge1	Towns (IOI15_towns)	C++11	25 / 100	26 ms	400 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, best = 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 = 1; i < N; i++) {
                if (best < dist(a, i)) best = dist(a, i), b = i;
        }
        for (int i = 1; i < N; i++) {
                if (best < dist(i, b)) best = dist(i, b), a = i;
        }
        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;

        int da = dist(a, c) + dist(a, b) - dist(b, c);
        int db = dist(a, b) + dist(b, c) - dist(a, c);
        int dc = dist(a, c) + dist(b, c) - dist(a, b);

        if (sub == 3) {
                for (int i = 0; i < N; i++) g[i] = i;
                for (int i = 0; i < N; i++) {
                        for (int j = i + 1; j < N; j++) {
                                bool same_group = 0;
                                int xa = dist(i, a) + dist(j, a) - dist(i, j);
                                int xb = dist(i, b) + dist(j, b) - dist(i, j);
                                int xc = dist(i, c) + dist(j, c) - dist(i, j);
                                same_group = xa > da || xb > db || xc > dc;
                                if (same_group) g[j] = g[i];
                        }
                }
                for (int i = 0; i < N; i++) cnt[g[i]]++;
                for (int i = 0; i < N; i++) {
                        if (cnt[i] > N / 2) return res / 2;
                }
                return -res / 2;
        }
        for (int i = 0; i < N; i++) {
                int iab = dist(i, a) + dist(i, b) - dist(a, b);
                int iac = dist(i, a) + dist(i, c) - dist(a, c);
                int ibc = dist(i, b) + dist(i, c) - dist(b, c);
                if (iab == iac) {
                        cnt[a]++;
                } else if (iab == ibc) {
                        cnt[b]++;
                } else if (iac == ibc) {
                        cnt[c]++;
                }
        }
        for (int i = 0; i < N; i++) {
                if (cnt[i] > N / 2) return res / 2;
        }
        return -res / 2;
}

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