Submission #1006833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006833		Belphegor	Towns (IOI15_towns)	C++14	25 / 100	10 ms	608 KiB

towns

#include "towns.h"
#include<bits/stdc++.h>
using namespace std;
int D[305][305];
int hubDistance(int N, int sub) {
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++) D[i][j] = -1;
		D[i][i] = 0;
	}
	for(int i=1; i<N; i++) D[0][i] = D[i][0] = getDistance(0,i);
	int a = 1;
	for(int i=2; i<N; i++) if(D[0][a] < D[0][i]) a = i;
	for(int i=1; i<N; i++){
		if(i == a) continue;
		D[a][i] = D[i][a] = getDistance(a,i);
	}
	int b = a;
	for(int i=0; i<N; i++){
		if(D[i][a] > D[b][a]) b = i;
	}
	int diameter = D[a][b];
	map<int,vector<int>>m;
	for(int i=1; i<N; i++){
		if(i == a) continue;
		int d = D[a][i] + D[0][a] - D[i][0]; d >>= 1;
		m[d].emplace_back(i);
	}
	m.begin()->second.emplace_back(a);
	m.rbegin()->second.emplace_back(0);
	int center_dist = D[a][b] + D[0][a] - D[0][b]; center_dist >>= 1;
	int R = INT32_MAX;
	for(auto it : m){
		int d = it.first;
		if(d > center_dist) continue;
		R = min(R, max(d,diameter - d));	
	}
	int before = 0;

	for(auto it : m){
		int d = it.first;
		if(d > center_dist){
			//all large cities from now on can't be hubs
			break;
		}
		if(max(d,diameter - d) != R){
			before+=it.second.size();
			continue;
		}
		
		int sz = it.second.size();
		if(sz > N/2){
			//determine
			vector<vector<int>>G;
			vector<int>T;
			int vote = 0;
			
			for(int y : it.second){
				if(T.empty()){
                       T.emplace_back(y);
                       vote++;
                   }
				else{
					int x = T[0];
					if( D[x][a] + D[y][a] - 2*d > getDistance(x,y) ) vote++;
					else{
                        T.emplace_back(y);
						vote--;
						if(!vote){
							G.emplace_back(T);
							T.clear();
						}
					}
				}
			}
			G.emplace_back(T);
			if(vote){
				//maybe there's majority
				int major = G.back()[0];
				vote += G.back().size() - 1;
				G.pop_back();
				for(auto v : G){
					int x = v[0];
					if(D[x][a] + D[major][a] - 2*d > getDistance(x,major))
						vote+=v.size()-1;
					else{
						for(int j=1; j<v.size(); j++){
							int cur = v[j];
							if(D[cur][a] + D[major][a] - 2*d > getDistance(cur,major))
								vote++;
						}
					}
				}
				if(vote <= N/2) return -R;
			}
			return R;
		}
		else{
			if(before <= N/2 && N - before - sz <= N/2){
				//balanced
				return R;
			}
		}
		before+=sz;
	}
	return -R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:46:27: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   46 |    before+=it.second.size();
      |                           ^
towns.cpp:50:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   50 |   int sz = it.second.size();
      |            ~~~~~~~~~~~~~~^~
towns.cpp:79:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   79 |     vote += G.back().size() - 1;
      |                               ^
towns.cpp:84:22: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   84 |       vote+=v.size()-1;
      |                      ^
towns.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |       for(int j=1; j<v.size(); j++){
      |                    ~^~~~~~~~~
towns.cpp:5:28: warning: unused parameter 'sub' [-Wunused-parameter]
    5 | 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