제출 #1271705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271705		vtnoo	Towns (IOI15_towns)	C++20	0 / 100	8 ms	328 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());
	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());
	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);
	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: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39