Submission #387295

#	Time	Username	Problem	Language	Result	Execution time	Memory
387295		Keshi	Towns (IOI15_towns)	C++17	0 / 100	19 ms	364 KiB

towns

//In the name of God
#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

int d[3][maxn], dis[maxn], sz[maxn], h[maxn];

int solve3(int n){
	return 0;
}

int solve4(int n){
	ll v = 0;
	for(ll i = 1; i < n; i++){
		d[0][i] = getDistance(0, i);
		if(d[0][i] > d[0][v]) v = i;
	}
	ll u = v;
	for(ll i = 0; i < n; i++){
		/*if(i == v) continue;
		if(i == 0){
			d[1][0] = d[0][v];
			continue;
		}*/
		d[1][i] = getDistance(v, i);
		if(d[1][i] > d[1][u]) u = i;
	}
	for(ll i = 0; i < n; i++){
		/*if(i == u) continue;
		if(i == 0){
			d[2][0] = d[0][u];
			continue;
		}
		if(i == v){
			d[2][v] = d[1][u];
			continue;
		}*/
		d[2][i] = getDistance(u, i);
	}
	ll D = d[1][u];
	map<ll, ll> mp;
	ll t = 1;
//	cout << "# " << v << " " << u << "\n";
	for(ll i = 0; i < n; i++){
		h[i] = (d[1][i] + d[2][i] - D) / 2;
//		cout << h[i] << " " << d[1][i] << " -> " << d[1][i] - h[i] << "\n";
		if(!mp[d[1][i] - h[i]]){
			mp[d[1][i] - h[i]] = t;
			dis[t] = d[1][i] - h[i];
			sz[t] = 0;
			t++;
		}
		sz[mp[d[1][i] - h[i]]]++;
	}
	ll R = inf;
	bool f = 0;
	for(ll i = 1; i < t; i++){
		R = min(R, max(dis[i], D - dis[i]));
		if(sz[i] > n / 2) f = 1;
	}
	if(f) R *= -1;
	return R;
}

int hubDistance(int n, int sub) {
	if(sub == 3) return solve3(n);
	return solve4(n);
}

/*int main(){
    fast_io;



    return 0;
}*/

Compilation message (stderr)

towns.cpp: In function 'int solve3(int)':
towns.cpp:24:16: warning: unused parameter 'n' [-Wunused-parameter]
   24 | int solve3(int n){
      |            ~~~~^

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