Submission #1091413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091413		Zicrus	Towns (IOI15_towns)	C++17	38 / 100	14 ms	1116 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);
}
 
vector<int> lnk, sz;
 
int find(int a) {
    if (lnk[a] != a) return lnk[a] = find(lnk[a]);
    return lnk[a];
}
 
void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    lnk[a] = b;
    sz[b] += sz[a];
}
 
int hubDistance(int n, int sub) {
    if (sub == 2) {
        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;
    }
    
    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;
    unordered_map<ll, vector<ll>> hubs;
    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);
        if (val < res) hubs.clear();
        if (val <= res) {
            res = val;
            hubs[distA].push_back(i);
        }
    }
    ll bad = 0;
    for (auto &e : hubs) {
        sz = vector<int>(n, 1);
        lnk = vector<int>(n);
        for (int i = 0; i < n; i++) lnk[i] = i;
        for (auto &x : e.second) {
            ll distX = getDist(x, a) - e.first;
            for (auto &y : e.second) {
                if (find(x) == find(y)) continue;
                ll distY = getDist(y, a) - e.first;
                if (getDist(x, y) < distX + distY) {
                    unite(x, y);
                }
            }
        }
        ll low = 0, high = 0;
        for (int i = 0; i < n; i++) {
            ll distA = getDist(i, a);
            ll distB = getDist(i, b);
            ll nw = (distA + distB - mxDist) / 2;
            distA -= nw;
            if (distA < e.first) low++;
            if (distA > e.first) high++;
        }
        if (low > n/2 || high > n/2) {
            bad++;
            continue;
        }
        bool no = false;
        for (int i = 0; i < n; i++) {
            if (lnk[i] != i) continue;
            if (sz[i] > n/2) no = true;
        }
        if (no) bad++;
    }
    return bad == hubs.size() ? -res : res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:45:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   45 |             ll val = getDist(a, i);
      |                              ^
towns.cpp:54:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   54 |             ll distA = getDist(i, a);
      |                                   ^
towns.cpp:55:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   55 |             ll distB = getDist(i, b);
      |                                   ^
towns.cpp:66:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   66 |             ll distA = getDist(i, a);
      |                                   ^
towns.cpp:67:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   67 |             ll distB = getDist(i, b);
      |                                   ^
towns.cpp:83:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   83 |         for (int i = mxDist; i >= 0; i--) {
      |                      ^~~~~~
towns.cpp:87:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   87 |         return hubs.empty() ? -res : res;
      |                ~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:102:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  102 |         ll val = getDist(a, i);
      |                          ^
towns.cpp:112:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |         ll distA = getDist(i, a);
      |                               ^
towns.cpp:113:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  113 |         ll distB = getDist(i, b);
      |                               ^
towns.cpp:130:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  130 |             ll distX = getDist(x, a) - e.first;
      |                                ^
towns.cpp:130:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  130 |             ll distX = getDist(x, a) - e.first;
      |                                   ^
towns.cpp:132:26: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |                 if (find(x) == find(y)) continue;
      |                          ^
towns.cpp:132:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |                 if (find(x) == find(y)) continue;
      |                                     ^
towns.cpp:133:36: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  133 |                 ll distY = getDist(y, a) - e.first;
      |                                    ^
towns.cpp:133:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  133 |                 ll distY = getDist(y, a) - e.first;
      |                                       ^
towns.cpp:134:29: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |                 if (getDist(x, y) < distX + distY) {
      |                             ^
towns.cpp:134:32: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  134 |                 if (getDist(x, y) < distX + distY) {
      |                                ^
towns.cpp:135:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  135 |                     unite(x, y);
      |                           ^
towns.cpp:135:30: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  135 |                     unite(x, y);
      |                              ^
towns.cpp:141:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  141 |             ll distA = getDist(i, a);
      |                                   ^
towns.cpp:142:35: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  142 |             ll distB = getDist(i, b);
      |                                   ^
towns.cpp:159:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::unordered_map<long long int, std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     return bad == hubs.size() ? -res : res;
      |            ~~~~^~~~~~~~~~~~~~
towns.cpp:159:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  159 |     return bad == hubs.size() ? -res : res;
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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