제출 #1272874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272874		vtnoo	Towns (IOI15_towns)	C++20	13 / 100	9 ms	1860 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+1>N/2){
			cand=key;
			break;
		}
	}
	/* cout<<a<<" "<<b<<endl;
	cout<<cand<<endl; */
	if(cand==-1){
		return R;
	}
	auto v=mp[cand];
	/* for(int i=0;i<(int)v.size();i++)cout<<v[i]<<" ";
	cout<<endl;
	for(int i=0;i<(int)v.size();i++)cout<<h[v[i]]<<" ";
	cout<<endl; */
	vector<int> treeSizes;
	vector<bool> vis(N, false);
	for(int i=0;i<(int)v.size();i++){
		int x=v[i];
		if(vis[x])continue;
		vis[x]=true;
		int currTree=1;
		for(int j=0;j<(int)v.size();j++){
			int y=v[j];
			if(vis[y])continue;
			if(getDistance(x, y)!=h[x]+h[y]){
				vis[y]=true;
				currTree++;
			}
		}
		treeSizes.push_back(currTree);
	}
	/* for(int i=0;i<(int)treeSizes.size();i++)cout<<treeSizes[i]<<" ";
	cout<<endl; */
	bool ok=true;
	for(int i=0;i<(int)treeSizes.size();i++){
		if(treeSizes[i]>N/2){
			ok=false;
			break;
		}
	}
	if(ok&&N-pref-1<=N/2){
		return R;
	}
	return -R;
}

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