Submission #616986

#	Time	Username	Problem	Language	Result	Execution time	Memory
616986		Lucpp	Towns (IOI15_towns)	C++17	35 / 100	18 ms	980 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())

int hubDistance(int n, int sub) {
	sub--; // suppress unused warning
	vector<int> d0(n), du(n);
	for(int i = 1; i < n; i++) d0[i] = getDistance(0, i);
	int u = int(max_element(d0.begin(), d0.end())-d0.begin());
	for(int i = 0; i < n; i++) if(u!=i) du[i] = getDistance(u, i);
	int v = int(max_element(du.begin(), du.end())-du.begin());
	int l = 0, r = 0;
	vector<int> xl, xr;
	int maxB = 0, maxC = 0;
	for(int i = 0; i < n; i++){
		int b = (d0[u]+d0[i]-du[i])/2;
		int c = d0[u]-b;
		if(b+du[v]-d0[u] <= du[v]/2){
			if(b < maxB) l++;
			if(b > maxB) l+=sz(xl), xl.clear(), maxB = b;
			if(b == maxB) xl.push_back(i);
		}
		if(c <= du[v]/2){
			if(c < maxC) r++;
			if(c > maxC) r+=sz(xr), xr.clear(), maxC = c;
			if(c == maxC) xr.push_back(i);
		}
	}
	int R = min(d0[u]-maxB, du[v]-maxC);
	vector<int> x;
	bool ok = false;
	// cerr << maxB << " " << maxC << " " << l << " " << r << " " << sz(xl) << " " << sz(xr) << "\n";
	if(d0[u]-maxB == R){
		if(l <= n/2 && r+sz(xr) <= n/2) x = xl, ok = true;
	}
	if(du[v]-maxC == R){
		if(l+sz(xl) <= n/2 && r <= n/2) x = xr, ok = true;
	}
	if(xl == xr){
		if(l <= n/2 && r <= n/2) x = xl, ok = true;
	}
	if(!ok || sz(x) > n/2) return -R;
	else return R;
	// auto same = [&](int a, int b){
	// 	return getDistance(a, b) == (d0[a]+du[a]-d0[u])/2 + (d0[b]+du[b]-d0[u])/2;
	// };
	// vector<int> cache(sz(x), -1);
	// int cnt = 1;
	// int cur = 0;
	// cache[0] = 0;
	// for(int i = 1; i < sz(x); i++){
	// 	if(same(x[cur], x[i])) cnt++, cache[i] = cur;
	// 	else if(--cnt == 0){
	// 		cur = i;
	// 		cnt = 1;
	// 		cache[i] = cur;
	// 	}
	// }
	// int other = 0;
	// bool isSame = false;
	// for(int i = 0; i < sz(x); i++){
	// 	if(other >= (n+1)/2) break;
	// 	if(cache[i] == i){
	// 		if(isSame) isSame = false;
	// 		else isSame = same(cur, x[i]);
	// 	}
	// 	if(cache[i] != -1 && !isSame) other++;
	// 	if(cache[i] == -1 && isSame) other++;
	// 	if(cache[i] == -1 && !isSame) other += !same(cur, x[i]);
	// }
	// if(sz(x)-other <= n/2) return R;
	// else 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