Submission #798575

#	Time	Username	Problem	Language	Result	Execution time	Memory
798575		Username4132	Towns (IOI15_towns)	C++14	25 / 100	22 ms	732 KiB

towns

#include "towns.h"
#include<iostream>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)

const int MAXN = 120;
int n, dis, mx, v=-1, w=-1, d1[MAXN], d2[MAXN];

inline int calc(int ver){
	return (mx+d2[ver]-d1[ver])>>1;
}

int hubDistance(int N, int sub) {
	n=N;
	forn(i, n) d1[i]=d2[i]=0;
	mx=-1;
	forsn(i, 1, n){
		d1[i]=getDistance(0, i);
		if(mx<d1[i]) mx=d1[i], v=i;
	}
	dis=-1;
	forn(i, n) if(i!=v){
		d2[i]=getDistance(v, i);
		if(dis<d2[i]) dis=d2[i], w=i;
	}

	int cc = calc(w);
	int ans = 1000000000;
	forn(i, n){
		int d = calc(i);
		if(d<=cc){
			ans = min(ans, max(d, dis-d));
		}
	}
	return ans;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:14:28: warning: unused parameter 'sub' [-Wunused-parameter]
   14 | 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