Submission #798615

#	Time	Username	Problem	Language	Result	Execution time	Memory
798615		Username4132	Towns (IOI15_towns)	C++14	100 / 100	14 ms	1068 KiB

towns

#include "towns.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

const int MAXN = 120;
int n, dis, mx, v=-1, w=-1, d1[MAXN], d2[MAXN], hdi[MAXN];

inline int calc(int ver){
	return (mx+d2[ver]-d1[ver])>>1;
}

inline bool check(int i, int j){
	return getDistance(i, j) < hdi[i] + hdi[j];
}

pii solve(vector<int>& vec, int l){
	if(l==(int)vec.size()) return {-1, -1};
	vector<int> eq, di;
	eq.PB(vec[l]);
	int cur=l+1;
	while(cur<(int)vec.size() && eq.size()!=di.size()){
		if(check(vec[l], vec[cur])) eq.PB(vec[cur]);
		else di.PB(vec[cur]);
		++cur;
	}
	if(eq.size()!=di.size()) return {vec[l], eq.size()};
	pii val = solve(vec, cur);
	if(val.F==-1) return {-1, -1};
	if(check(vec[l], val.F)) return {vec[l], val.S + eq.size()};
	int cou=val.S;
	for(int el:di) cou+=check(el, val.F);
	if(2*cou>((int)vec.size())-l) return {val.F, cou};
	else return {-1, -1};
}

bool test(int d){
	int x=0, y=0;
	vector<int> us;
	forn(i, n){
		int nd = calc(i);
		if(nd>d) ++x;
		else if(nd<d) ++y;
		else us.PB(i);
	}
	if(x>(n/2) || y>(n/2)) return false;
	for(int el:us) hdi[el]=d2[el]-calc(el);
	pii ret = solve(us, 0);
	return ret.S<=(n/2);
}

int hubDistance(int N, int sub) {
	n=N;
	forn(i, n) d1[i]=d2[i]=0;
	mx=-1;
	forsn(i, 1, n){
		d1[i]=getDistance(0, i);
		if(mx<d1[i]) mx=d1[i], v=i;
	}
	dis=-1;
	forn(i, n) if(i!=v){
		d2[i]=getDistance(v, i);
		if(dis<d2[i]) dis=d2[i], w=i;
	}

	int cc = calc(w);
	int ans = 1000000000;
	forn(i, n){
		int d = calc(i);
		if(d<=cc) ans = min(ans, max(d, dis-d));
	}

	vector<int> used;
	bool yes=false;
	forn(i, n){
		int d = calc(i);
		if(max(d, dis-d)==ans && find(used.begin(), used.end(), d)==used.end()) yes|=test(d), used.PB(d);
	}

	return (yes? ans : -ans);
}

Compilation message (stderr)

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

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