Submission #1272868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272868		vtnoo	Towns (IOI15_towns)	C++20	25 / 100	10 ms	1856 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), h(N, 1e9);
	map<int, vector<int>> mp;
	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;
		mp[d1].push_back(i);
		h[i]=e[i]-d1;
		r[i]=max(d1, d2);
	}
	int R=*min_element(r.begin(), r.end());
	if(sub<=2)return R;
	int pref=0, cand=-1;
	for(auto [key, v]:mp){
		pref+=v.size();		
		if(pref>N/2){
			cand=key;
			break;
		}
	}
	if(cand==-1){
		return R;
	}
	auto v=mp[cand];
	vector<int> treeSizes;
	vector<bool> vis(N, false);
	for(int i=0;i<(int)v.size();i++){
		int a=v[i];
		if(vis[a])continue;
		vis[a]=true;
		int currTree=1;
		for(int j=0;j<(int)v.size();j++){
			int b=v[j];
			if(vis[b])continue;
			if(getDistance(a, b)!=h[a]+h[b]){
				vis[b]=true;
				currTree++;
			}
		}
		treeSizes.push_back(currTree);
	}
	bool ok=true;
	for(int i=0;i<(int)treeSizes.size();i++){
		if(treeSizes[i]>N/2){
			ok=false;
			break;
		}
	}
	if(ok&&N-pref<=N/2){
		return R;
	}
	return -R;
}

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