Submission #235733

#	Time	Username	Problem	Language	Result	Execution time	Memory
235733		ryansee	Towns (IOI15_towns)	C++14	100 / 100	32 ms	512 KiB

towns

// this isn't mine, I'm just asserting something
#include "towns.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ii = pair<int, int>;
 
#define X first
#define Y second
 
int v = 0, s, t, r;
int distv[120], dists[120];
 
bool sameConn(int x1, int x2) {
	int x = getDistance(x1, x2);
	return (dists[x1] + dists[x2] - x > 2 * r);
}
 
int hubDistance(int N, int sub) {
	int maxv = 0;
	for(int i = 0 ; i < N ; i++) {
		distv[i] = getDistance(v, i);
		maxv = max(maxv, distv[i]);
	}
	
	for(int i = 0 ; i < N ; i++)
		if(distv[i] == maxv)
			s = i;
			
	int dsv = maxv;
			
	maxv = 0;
	for(int i = 0 ; i < N ; i++) {
		dists[i] = getDistance(s, i);
		maxv = max(maxv, dists[i]);
	}
	
	int d = maxv;
	
	for(int i = 0 ; i < N ; i++)
		if(dists[i] == maxv)
			t = i;	
 
	int res = 1e9;
	vector<int> poss;
	for(int i = 0 ; i < N ; i++) {
		int a = (dists[i] + dsv - distv[i]) / 2;
		int b = dsv - a;
		if(max({a, b, d - a}) < res) {
			res = max({a, b, d - a});
			poss.clear();
			poss.push_back(a);
		} else if(max({a, b, d - a}) == res)
			poss.push_back(a);
		//~ cout << i << " " << res << endl;
	}
	
	vector<int> B;
	for(int i = 0 ; i < N ; i++)
		B.push_back((dists[i] + dsv - distv[i]) / 2);
		
	sort(B.begin(), B.end());
	
	int m;
	if(B.size() % 2 == 0) {
		int m1 = B[B.size() / 2 - 1];
		int m2 = B[B.size() / 2];
		if(m1 == m2)
			m = m1;
		else {
			if(find(poss.begin(), poss.end(), m1) == poss.end()
				&& find(poss.begin(), poss.end(), m2) == poss.end()) {
				//~ cout << "aa" << endl;
				return -res;
			}		
			return res;
		}
	} else
		m = B[B.size() / 2];
		
	if(find(poss.begin(), poss.end(), m) == poss.end()) {
		//~ cout << "aa" << endl;
		return -res;
	}
	r = m;
		
	vector<int> list, bucket;
	for(int i = 0 ; i < N ; i++) {
		if((dists[i] + dsv - distv[i]) / 2 == m) {
			if(list.empty() || !sameConn(i, list.back())) {
				list.push_back(i);
				if(!bucket.empty()) {
					list.push_back(bucket.back());
					bucket.pop_back();
				}
			} else
				bucket.push_back(i);
		}
	}
		
	int T = list.back();
		
	int cnt = 0;
	while(!list.empty()) {
		if(sameConn(list.back(), T)) {
			cnt++;
			if(list.size() > 1) {
				list.pop_back();
				list.pop_back();
			} else {
				++cnt;
				list.pop_back();
			}
		} else {
			list.pop_back();
		}
	}
	
	cnt += bucket.size();
	
	if(cnt <= N / 2) {
		//~ cout << "c" << endl;
		return res;
	}
	//~ cout << "ab" << endl;
	return -res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:120:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  cnt += bucket.size();
                     ^
towns.cpp:20:28: warning: unused parameter 'sub' [-Wunused-parameter]
 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