Submission #434676

#	Time	Username	Problem	Language	Result	Execution time	Memory
434676		Tangent	Towns (IOI15_towns)	C++17	0 / 100	20 ms	452 KiB

towns

#include "towns.h"
#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

map<pii, int> memo;
int dist(int u, int v) {
	if (!memo[{u, v}]) {
		memo[{u, v}] = memo[{v, u}] = getDistance(u, v);
	}
	return memo[{u, v}];
}

int hubDistance(int n, int sub) {
	int res = 1000000000;
	memo.clear();
	
	int furthest = 1, maxdist = dist(0, 1);
	ffor(i, 2, n) {
		if (dist(0, i) > maxdist) {
			maxdist = dist(0, i);
			furthest = i;
		}
	}
	int furthest2 = 0;
	maxdist = dist(furthest, 0);
	ffor(i, 1, n) {
		if (i != furthest && dist(furthest, i) > maxdist) {
			maxdist = dist(furthest, i);
			furthest2 = i;
		}
	}

	map<int, int> xs;
	ffor(j, 1, n) {
		if (j == furthest2) {
			continue;
		}
		int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
		int x = (a + c - b) / 2, y = (b + c - a) / 2;
		xs[x] = max(xs[x], y);
	}
	forin(p, xs) {
		int curr = max(max(p.second, p.first), dist(furthest, furthest2) - p.first);
		forin(p2, xs) {
			if (p != p2) {
				curr = max(curr, abs(p2.first - p.first) + p2.second);
			}
		}
		res = min(res, curr);
	}

	return res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:38:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   38 |   if (dist(0, i) > maxdist) {
      |               ^
towns.cpp:39:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   39 |    maxdist = dist(0, i);
      |                      ^
towns.cpp:40:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   40 |    furthest = i;
      |               ^
towns.cpp:46:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   46 |   if (i != furthest && dist(furthest, i) > maxdist) {
      |                                       ^
towns.cpp:47:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   47 |    maxdist = dist(furthest, i);
      |                             ^
towns.cpp:48:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |    furthest2 = i;
      |                ^
towns.cpp:57:58: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   57 |   int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
      |                                                          ^
towns.cpp:57:81: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   57 |   int a = dist(furthest, furthest2), b = dist(furthest2, j), c = dist(furthest, j);
      |                                                                                 ^
towns.cpp:32:28: warning: unused parameter 'sub' [-Wunused-parameter]
   32 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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