Submission #749408

#	Time	Username	Problem	Language	Result	Execution time	Memory
749408		Abrar_Al_Samit	도시들 (IOI15_towns)	C++17	25 / 100	23 ms	980 KiB

towns

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

const int nax = 110;

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

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

	int d = getDistance(u, v);
	return d != a[u]+a[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(), i)) {
			list.push_back(i);
			if(!bucket.empty()) {
				list.push_back(bucket.back());
				bucket.pop_back();
			}
		} else {
			bucket.push_back(i);
		}
	}

	int T = list.back();

	while(list.size()>1) {
		if(EQUAL(T, list.back())) {
			list.pop_back();
			list.pop_back();
		} else {
			list.pop_back();
			if(bucket.empty()) return 1;
			bucket.pop_back();
		}
	}
	return (!list.empty() || !bucket.empty()) ? -1 : 1;
}
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);

		a[i] = a_plus_b - b;
	}

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

	return Do_The_Majority_Thing(groups[big]) * 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: In function 'int hubDistance(int, int)':
towns.cpp:89:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |   if(it.second.size()>N/2) {
      |      ~~~~~~~~~~~~~~~~^~~~
towns.cpp:50:28: warning: unused parameter 'sub' [-Wunused-parameter]
   50 | 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