Submission #140590

#	Time	Username	Problem	Language	Result	Execution time	Memory
140590		SirCeness	Towns (IOI15_towns)	C++14	25 / 100	23 ms	1016 KiB

towns

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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x)  "(" << x.first << ", " << x.second << ") "
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

int mat[150][150];

int n; 

int getdistance(int node1, int node2){
	if (mat[node1][node2] != -1) return mat[node1][node2];
	int ans = getDistance(node1, node2);
	mat[node1][node2] = ans;
	mat[node2][node1] = ans;
	return ans;
}


int getmaxdist(int node){
	int ans = node;
	int dist = 0;
	for (int i = 0; i < n; i++){
		if (i == node) continue;
		int res = getdistance(node, i);
		if (res > dist){
			dist = res;
			ans = i;
		}
	}
	return ans;
}



int hubDistance(int N, int sub) {
	
	for (int i = 0; i < 150; i++) for (int j = 0; j < 150; j++) mat[i][j] = -1;
	
	n = N;
	int node1 = getmaxdist(0);
	int node2 = getmaxdist(node1);
	int r = 100000000;
	int dist = getdistance(node1, node2);
	//cout << bas(node1) << bas(node2) << bas(dist) << endl;
	for (int i = 0; i < n; i++){
		if (i == node1 || i == node2) continue;
		int d1 = getdistance(i, node1);
		int d2 = getdistance(i, node2);
		int uzak = (d1+d2-dist)/2;
		int uzak1 = d1-uzak;
		int uzak2 = d2-uzak;
		//cout << bas(i) << bas(uzak1) << bas(uzak2) << bas(uzak) << endl;
		int rtmp = max(max(uzak, uzak1), uzak2);
		r = min(r, rtmp);
	}
	return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:47:28: warning: unused parameter 'sub' [-Wunused-parameter]
 int hubDistance(int N, int sub) {
                            ^~~

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