Submission #434548

#	Time	Username	Problem	Language	Result	Execution time	Memory
434548		Tangent	Towns (IOI15_towns)	C++17	0 / 100	24 ms	844 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 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;
		}
	}
	int res = 10000000;
	rep(i, N) {
		if (i != furthest && i != furthest2) {
			res = min(res, (abs(dist(furthest2, i) - dist(furthest, i)) + dist(furthest, furthest2)) / 2);
		}
	}

	return res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:35:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   35 |   if (dist(0, i) > maxdist) {
      |               ^
towns.cpp:36:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   36 |    maxdist = dist(0, i);
      |                      ^
towns.cpp:37:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   37 |    furthest = i;
      |               ^
towns.cpp:44:39: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   44 |   if (i != furthest && dist(furthest, i) > maxdist) {
      |                                       ^
towns.cpp:45:29: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   45 |    maxdist = dist(furthest, i);
      |                             ^
towns.cpp:46:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   46 |    furthest2 = i;
      |                ^
towns.cpp:52:40: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |    res = min(res, (abs(dist(furthest2, i) - dist(furthest, i)) + dist(furthest, furthest2)) / 2);
      |                                        ^
towns.cpp:52:60: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   52 |    res = min(res, (abs(dist(furthest2, i) - dist(furthest, i)) + dist(furthest, furthest2)) / 2);
      |                                                            ^
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