Submission #1072424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072424		Zicrus	Towns (IOI15_towns)	C++17	25 / 100	19 ms	1112 KiB

towns

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

typedef long long ll;

unordered_map<ll, int> cache;

int getDist(int a, int b) {
    if (a == b) return 0;
    if (a < b) swap(a, b);
    ll hash = ((ll)a << 31) | b;
    if (cache.count(hash)) return cache[hash];
    return cache[hash] = getDistance(a, b);
}

int hubDistance(int n, int sub) {
    cache.clear();
    ll a = 0, b = 0;
    ll mxDist = 0;
    for (int i = 1; i < n; i++) {
        ll val = getDist(0, i);
        if (val > mxDist) {
            mxDist = val;
            a = i;
        }
    }
    mxDist = 0;
    for (int i = 0; i < n; i++) {
        ll val = getDist(a, i);
        if (val > mxDist) {
            mxDist = val;
            b = i;
        }
    }
    ll res = 1ll << 62ll;
    for (int i = 0; i < n; i++) {
        if (i == a || i == b) continue;
        ll distA = getDist(i, a);
        ll distB = getDist(i, b);
        ll nw = (distA + distB - mxDist) / 2;
        distA -= nw;
        distB -= nw;
        ll val = max(distA, distB);
        res = min(res, val);
    }
    vector<int> deg(mxDist+1);
    deg.front() = deg.back() = 1;
    for (int i = 0; i < n; i++) {
        if (i == a || i == b) continue;
        ll distA = getDist(i, a);
        ll distB = getDist(i, b);
        ll nw = (distA + distB - mxDist) / 2;
        distA -= nw;
        deg[distA]++;
    }
    unordered_set<ll> hubs;
    for (int i = 0; i < n; i++) {
        int d = max(i, (int)mxDist-i);
        if (d == res) hubs.insert(i);
    }
    ll sum = 0;
    for (int i = 0; i <= mxDist; i++) {
        if (sum > n/2 && hubs.count(i)) hubs.erase(i);
        sum += deg[i];
    }
    sum = 0;
    for (int i = mxDist; i >= 0; i--) {
        if (sum > n/2 && hubs.count(i)) hubs.erase(i);
        sum += deg[i];
    }
    return hubs.empty() ? -res : res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:30:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   30 |         ll val = getDist(a, i);
      |                          ^
towns.cpp:39:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   39 |         ll distA = getDist(i, a);
      |                               ^
towns.cpp:40:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   40 |         ll distB = getDist(i, b);
      |                               ^
towns.cpp:51:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   51 |         ll distA = getDist(i, a);
      |                               ^
towns.cpp:52:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |         ll distB = getDist(i, b);
      |                               ^
towns.cpp:68:18: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |     for (int i = mxDist; i >= 0; i--) {
      |                  ^~~~~~
towns.cpp:72:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   72 |     return hubs.empty() ? -res : res;
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:17:28: warning: unused parameter 'sub' [-Wunused-parameter]
   17 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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