Submission #749435

#	Time	Username	Problem	Language	Result	Execution time	Memory
749435		Abrar_Al_Samit	Towns (IOI15_towns)	C++17	25 / 100	14 ms	360 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"
using namespace std;

const int nax = 110;

int from0[nax];
int fromu[nax];
int c[nax];
int u, v;

bool EQUAL(int u, int v) {
	if(u==v) return true;

	int d = getDistance(u, v);
	return d != c[u]+c[v];
}
int Do_The_Majority_Thing(vector<int>v) {
	// http://www.cs.yale.edu/publications/techreports/tr252.pdf

	int n = v.size();

	vector<int>list, bucket;
	for(int i=0; i<n; ++i) {
		if(list.empty() || !EQUAL(list.back(), v[i])) {
			list.push_back(v[i]);
			if(!bucket.empty()) {
				list.push_back(bucket.back());
				bucket.pop_back();
			}
		} else {
			bucket.push_back(v[i]);
		}
	}

	int T = list.back();


	int cnt = 0;
	while(list.size()>1) {
		if(EQUAL(T, list.back())) {
			list.pop_back();
			list.pop_back();
		} else {
			list.pop_back();
			if(bucket.empty()) return 0;
			bucket.pop_back();
		}
		++cnt;
	}
	cnt += bucket.size();
	if(!list.empty() && EQUAL(list[0], T)) ++cnt;
	return cnt;
}
int hubDistance(int N, int sub) {
	int mx = 0;
	for(int i=1; i<N; ++i) {
		from0[i] = getDistance(0, i);
		if(mx<from0[i]) {
			mx = from0[i];
			u = i;
		}
	}

	mx = 0;
	for(int i=0; i<N; ++i) {
		fromu[i] = getDistance(i, u);
		if(fromu[i]>mx) {
			mx = fromu[i];
			v = i;
		}
	}

	int R = 2e9;
	map<int, vector<int>>groups;


	for(int i=0; i<N; ++i) {
		int a_plus_b = from0[u];
		int b_plus_c = fromu[i];
		int c_plus_a = from0[i];

		int b = (b_plus_c - c_plus_a + a_plus_b) / 2;
		int d = fromu[v] - b;

		R = min(R, max(b, d));
		groups[b].push_back(i);

		c[i] = b_plus_c - b;
	}

	int par = 2e9;
	for(int i=0; i<N; ++i) if(i!=u) {
		par = min(par, fromu[i]-c[i]);
	}
	groups[par].push_back(u);

	par = 2e9;
	for(int i=1; i<N; ++i) {
		int b = from0[u] - (from0[i]-c[i]);
		par = min(par, b);
	}
	groups[par].push_back(0);

	int big = -1;
	for(auto it : groups) {
		if(it.second.size()>N/2) {
			big = it.first;
		}
	}
	if(big==-1) return R;

	int mx_freq = Do_The_Majority_Thing(groups[big]);
	if(mx_freq>N/2) return -R;
	return R;
}

Compilation message (stderr)

towns.cpp: In function 'bool EQUAL(int, int)':
towns.cpp:12:23: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   12 | bool EQUAL(int u, int v) {
      |                   ~~~~^
towns.cpp:10:8: note: shadowed declaration is here
   10 | int u, v;
      |        ^
towns.cpp:12:16: warning: declaration of 'u' shadows a global declaration [-Wshadow]
   12 | bool EQUAL(int u, int v) {
      |            ~~~~^
towns.cpp:10:5: note: shadowed declaration is here
   10 | int u, v;
      |     ^
towns.cpp: In function 'int Do_The_Majority_Thing(std::vector<int>)':
towns.cpp:18:38: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   18 | int Do_The_Majority_Thing(vector<int>v) {
      |                           ~~~~~~~~~~~^
towns.cpp:10:8: note: shadowed declaration is here
   10 | int u, v;
      |        ^
towns.cpp:21:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   21 |  int n = v.size();
      |          ~~~~~~^~
towns.cpp:51:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |  cnt += bucket.size();
      |                     ^
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:107:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |   if(it.second.size()>N/2) {
      |      ~~~~~~~~~~~~~~~~^~~~
towns.cpp:55:28: warning: unused parameter 'sub' [-Wunused-parameter]
   55 | 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