Submission #1086988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086988		the_coding_pooh	Towns (IOI15_towns)	C++14	25 / 100	16 ms	1032 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

map <pair<int, int>, long long> mp;

long long dis(int a, int b){
	if(a == b) 
		return 0;
	if(a > b) 
		swap(a, b);
	if(mp.count({a, b})) 
		return mp[{a, b}];
	mp[{a, b}] = getDistance(a, b);
	return mp[{a, b}];
}

int hubDistance(int N, int sub) {
	mp.clear();
	int diam_u, diam_v;
	long long mx = 0;
	for(int i = 0; i < N; i++){
		if(dis(0, i) > mx){
			mx = dis(0, i);
			diam_u = i;
		}
	}
	mx = 0;
	for(int i = 0; i < N; i++){
		if(dis(diam_u, i) > mx){
			mx = dis(diam_u, i);
			diam_v = i;
		}
	}
	
	long long diam = dis(diam_u, diam_v), R;
	R = diam;
	for(int i = 0; i < N; i++){	
		long long a = dis(diam_u, i), b = dis(diam_v, i), delta;
		delta = (a + b - diam) / 2;
		R = min(R, max(a - delta, b - delta));
	}
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:45:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   45 |  return R;
      |         ^
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
   20 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp:38:22: warning: 'diam_u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |  long long diam = dis(diam_u, diam_v), R;
      |                   ~~~^~~~~~~~~~~~~~~~
towns.cpp:38:22: warning: 'diam_v' may be used uninitialized in this function [-Wmaybe-uninitialized]

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