Submission #233279

#	Time	Username	Problem	Language	Result	Execution time	Memory
233279		mieszko11b	Towns (IOI15_towns)	C++14	25 / 100	28 ms	896 KiB

towns

#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
			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<ii> X, D;
	for(int i = 0 ; i < N ; i++)
		if((dists[i] + dsv - distv[i]) / 2 == m)
			X.push_back({i, 1});
	
	//~ for(auto p : X)
		//~ cout << p.X << " ";
	//~ cout << endl;
	//~ for(int i = 0 ; i < X.size() ; i++) {
		//~ for(int j = 0 ; j < X.size() ; j++)
			//~ cout << sameConn(X[i].X, X[j].X) << " ";
		//~ cout << endl;
	//~ }
	//~ cout << endl;
			
	while(X.size() > 1) {
		if(X.size() % 2) {
			D.push_back(X.back());
			X.pop_back();
		} else {
			vector<ii> Y;
			for(int i = 0 ; i < X.size() ; i += 2) {
				if(sameConn(X[i].X, X[i + 1].X))
					Y.push_back({X[i].X, X[i].Y + X[i + 1].Y});
				else {
					D.push_back(X[i]);
					D.push_back(X[i + 1]);
				}
			}
			swap(X, Y);
		}
	}
	
	if(X.empty())
		return res;
		
	int cnt = X[0].Y;
	for(auto p : D) {
		if(sameConn(p.X, X[0].X)) 
			cnt += p.Y;
	}
	
	if(cnt <= N / 2)
		return res;
	//~ cout << "ab" << endl;
	return -res;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < X.size() ; i += 2) {
                    ~~^~~~~~~~~~
towns.cpp:19: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