Submission #1271706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271706		vtnoo	도시들 (IOI15_towns)	C++20	25 / 100	10 ms	464 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;

int hubDistance(int N, int sub) {
	vector<int> q(N);
	for(int i=1;i<N;i++){
		q[i]=getDistance(0,i);
	}
	int a=max_element(q.begin(), q.end())-q.begin();
	vector<int> w(N);
	for(int i=0;i<N;i++){
		if(i==a)continue;
		w[i]=getDistance(a,i);
	}
	int b=max_element(w.begin(), w.end())-w.begin();
	vector<int> e(N);
	// Tengo el diametro, ahora necesito computar para cada nodo su distancia a uno de ellos
	for(int i=0;i<N;i++){
		if(i==b)continue;
		e[i]=getDistance(b,i);
	}
	vector<int> r(N, 1e9);
	for(int i=0;i<N;i++){
		if(i==a||i==b)continue;
		int d1=((e[a]+e[i])-w[i])/2;
		int d2=((e[a]+w[i])-e[i])/2;
		r[i]=max(d1, d2);
	}
	return *min_element(r.begin(), r.end());
}

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