Submission #727167

#	Time	Username	Problem	Language	Result	Execution time	Memory
727167		becaido	Towns (IOI15_towns)	C++17	100 / 100	18 ms	408 KiB

towns

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

const int N = 111;

int n, A, B, cr;
int dis[N][N];
int d[N], r[N];

inline int D(int a, int b) {
    if (a == b) return 0;
    if (dis[a][b]) return dis[a][b];
    return dis[a][b] = dis[b][a] = getDistance(a, b);
}

inline bool same(int a, int b) {
    if (r[b] != cr) swap(a, b);
    if (r[a] < cr) return r[b] < cr;
    if (r[a] > cr) return r[b] > cr;
    return d[a] + d[b] != D(a, b);
}

int hubDistance(int N, int sub) {
    n = N;
    for (int i = 0; i < n; i++) fill(dis[i], dis[i] + n, 0);
    A = B = 0;
    for (int i = 0; i < n; i++) if (D(0, i) > D(0, A)) A = i;
    for (int i = 0; i < n; i++) if (D(A, i) > D(A, B)) B = i;
    int mn = INT_MAX;
    for (int i = 0; i < n; i++) {
        d[i] = (D(0, i) + D(A, i) - D(0, A)) / 2;
        r[i] = D(A, i) - d[i];
        mn = min(mn, max(r[i], D(A, B) - r[i]));
    }
    vector<int> vc;
    for (int i = 0; i < n; i++) if (max(r[i], D(A, B) - r[i]) == mn) vc.emplace_back(r[i]);
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end());
    if (vc.size() > 1) {
        int cnt = 0;
        for (int i = 0; i < n; i++) cnt += r[i] <= vc[0];
        if (cnt * 2 <= n) swap(vc[0], vc[1]);
    }
    cr = vc[0];
    vector<pair<int, int>> cur, die;
    for (int i = 0; i < n; i++) cur.emplace_back(i, 1);
    while (cur.size() > 1) {
        vector<pair<int, int>> tmp;
        for (int i = 0; i + 1 < cur.size(); i += 2) {
            if (same(cur[i].first, cur[i + 1].first)) tmp.emplace_back(cur[i].first, cur[i].second + cur[i + 1].second);
            else {
                if (cur[i].second < cur[i + 1].second) swap(cur[i], cur[i + 1]);
                if (cur[i].second == cur[i + 1].second) die.emplace_back(cur[i]), die.emplace_back(cur[i + 1]);
                else tmp.emplace_back(cur[i].first, cur[i].second - cur[i + 1].second), die.emplace_back(cur[i].first, cur[i + 1].second), die.emplace_back(cur[i + 1]);
            }
        }
        if (cur.size() & 1) tmp.emplace_back(cur.back());
        cur = tmp;
    }
    if (cur.size() == 0) return max(cr, D(A, B) - cr);
    int cnt = cur[0].second;
    for (auto [x, c] : die) if (same(cur[0].first, x)) cnt += c;
    return (cnt * 2 <= n ? 1 : -1) * max(cr, D(A, B) - cr);
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:26:21: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   26 | int hubDistance(int N, int sub) {
      |                 ~~~~^
towns.cpp:7:11: note: shadowed declaration is here
    7 | const int N = 111;
      |           ^
towns.cpp:52:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int i = 0; i + 1 < cur.size(); i += 2) {
      |                         ~~~~~~^~~~~~~~~~~~
towns.cpp:26:28: warning: unused parameter 'sub' [-Wunused-parameter]
   26 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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