Submission #727995

#	Time	Username	Problem	Language	Result	Execution time	Memory
727995		vjudge1	Towns (IOI15_towns)	C++11	13 / 100	19 ms	416 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<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);
                                }
                        }
                        if (cnt[a] > N / 2) continue;
                        if (cnt[b] > N / 2) continue;
                        if (notab.size() <= N / 2) return res;
                        vector<vector<int>> alive, dead;
                        vector<int> majority;
                        for (int j : notab) alive.push_back({j});
                        while (alive.size()) {
                                if (alive.size() == 1) {
                                        majority = alive[0];
                                        break;
                                }
                                if (alive.size() & 1) {
                                        dead.emplace_back(alive.back());
                                        alive.pop_back();
                                        continue;
                                }
                                vector<vector<int>> nalive;
                                for (int j = 0; j < alive.size(); j += 2) {
                                        if (dist(a, alive[j][0]) + dist(a, alive[j + 1][0]) - dist(alive[j][0], alive[j + 1][0]) > dist_hub) {
                                                nalive.push_back(alive[j]);
                                                nalive.back().insert(nalive.back().end(), alive[j + 1].begin(), alive[j + 1].end());
                                        } else {
                                                //                         dead.emplace_back(alive[j]);
                                                //                         dead.emplace_back(alive[j + 1]);
                                        }
                                }
                                alive = nalive;
                        }
                        if (majority.size() == 0) return res;
                        int sus = majority.size();
                        for (auto ded : dead) {
                                // if (dist(a, majority[0]) + dist(a, ded[0]) - dist(majority[0], ded[0]) > dist_hub) sus += ded.size();
                        }
                        if (sus <= N / 2) return res;
                }
        }

        return -res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:61:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |                         if (notab.size() <= N / 2) return res;
      |                             ~~~~~~~~~~~~~^~~~~~~~
towns.cpp:76:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                                 for (int j = 0; j < alive.size(); j += 2) {
      |                                                 ~~^~~~~~~~~~~~~~
towns.cpp:88:48: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   88 |                         int sus = majority.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: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39