Submission #96586

#	Time	Username	Problem	Language	Result	Execution time	Memory
96586		groeneprof	Towns (IOI15_towns)	C++14	35 / 100	132 ms	8312 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>

using namespace std;
vector<vector<int> > adj(120, vector<int> (120, -1));
int gD(int i, int j){
	if(i==j) return 0;
	if(adj[i][j]==-1){
		return adj[i][j] = adj[j][i] = getDistance(i, j);
	}
	return adj[i][j];
}
int hubDistance(int N, int sub) {
	adj.assign(120, vector<int> (120, -1));
	sub = sub*sub;
	//cout<<"haaaahaaaaaaaHHZHEAHJAHAAAAAAA"<<endl;
	int u=0, maxv = 0;
	for(int i =1; i<N; i++){
		if(gD(i, 0)>maxv){
			u = i;
			maxv = gD(i, 0);
		}
	}
	maxv = 0;
	int v = 0;
	for(int i = 0; i<N; i++) if(i!=u){
		if(gD(u, i)>maxv){
			v = i;
			maxv = gD(u, i);
		}		
	}
	//cout<<u<<" "<<v<<endl;
	vector<int> diam(2e6+5, 0);
	//int minimax = 1000000;
	for(int i = 0; i<N; i++){
		int x,y,z;
		x = gD(u, v);
		y = gD(u, i);
		z = gD(v, i);
		//cout<<i<<": "<<(x+y-z)/2<<endl;
		diam[(x+y-z)/2]++;
	}
	int R = 10000000;
	int Ri = 0;
	/*for(int i = 0; i<30; i++){
		cout<<diam[i]<<" ";
	}
	*/
	//cout<<endl;
	for(int i = 0; i<=gD(u,v); i++){
		if(diam[i]>0&&R>max(i, gD(u,v)-i)){
			R =  max(i , gD(u,v)-i);
			Ri = i;
			//cout<<"i: "<<i<<" R: "<<R<<endl;
		}
	}
	int boven = 0, onder = 0;
	for(int i = 0; i<(int)diam.size(); i++){
		if(i<Ri) onder+=diam[i];
		if(i>Ri) boven+=diam[i];
	}
	//cout<<boven<<" "<<onder<<endl;
	if(boven>N/2 || onder > N/2 || N-boven-onder>N/2) R = -R;
	return R;
}

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