Submission #623934

#	Time	Username	Problem	Language	Result	Execution time	Memory
623934		8e7	Towns (IOI15_towns)	C++17	13 / 100	15 ms	452 KiB

towns

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 155
#define pii pair<int, int>
#define ff first
#define ss second
#include "towns.h"


int n;
int save[maxn][maxn];
bool done[maxn][maxn];
int query(int u, int v) {
	if (u == v || u >= n || v >= n) return 0;
	if (done[u][v]) return save[u][v];
	save[u][v] = save[v][u] = getDistance(u, v);
	done[u][v] = done[v][u] = 1;
	return save[u][v];
}
int hubDistance(int N, int sub) {
	n = N;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) done[i][j] = 0;
	}
	vector<int> da, db, l(n), w(n), ws;
	int b = 0, ma = 0;
	for (int i = 0;i < n;i++) {
		da.push_back(query(0, i));	
		if (da.back() > ma) {
			ma = da.back();
			b = i;
		}
	}
	int len = ma;
	for (int i = 0;i < n;i++) {
		db.push_back(query(b, i));
		ma = max(ma, db.back());
	}
	//debug(ma);
	
	int R = 1<<30;
	for (int i = 0;i < n;i++) {
		l[i] = (da[i] + db[i] - len) / 2;	
		w[i] = db[i] - l[i];
		//debug(l[i], w[i]);
		ws.push_back(w[i]);
		R = min(R, max(w[i], ma - w[i]));
	}
	sort(ws.begin(), ws.end());
	ws.resize(int(unique(ws.begin(), ws.end()) - ws.begin()));
	int siz = ws.size();
	vector<vector<int> > col(siz, vector<int>());
	vector<int> pref(siz, 0), suf(siz, 0);
	for (int i = 0;i < n;i++) {
		int ind = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();	
		col[ind].push_back(i);
	}
	for (int i = 0;i < siz;i++) pref[i] = col[i].size() + (i ? pref[i-1] : 0);	
	for (int i = siz-1;i >= 0;i--) suf[i] = col[i].size() + (i < siz-1 ? suf[i+1] : 0);

	vector<int> vec, tmp;
	for (int i = 0;i < siz;i++) {
		int v = max(ws[i], ma - ws[i]);
		if (v == R) {
			if ((i == 0 || pref[i-1] <= n/2) && (i == siz-1 || suf[i+1] <= n/2) && col[i].size() <= n/2) {
				return R;
			} else if (col[i].size() > n/2) {
				vec = col[i];
				for (int j = 0;j < n - col[i].size();j++) vec.push_back(n+j);
			}
		}
	}
	tmp = vec;

	auto same = [&] (int i, int j) {
		int v = query(i, j);
		if (v == 0) return 0;
		int d = l[i] + l[j] - v;
		return d == 0 ? 1 : 0;
	};
	while (vec.size() > 1) {
		vector<int> nxt;
		for (int i = 0;i < vec.size();i += 2) {
			if (i == (int)vec.size()-1) {
				if (nxt.size() == 0) nxt.push_back(i);
			} else {
				if (same(vec[i], vec[i+1])) nxt.push_back(vec[i]); 
			}
		}
		vec = nxt;
	}
	if (vec.size() == 0) return R;
	else {
		int c = vec[0];
		int cnt = 1, bad = 0;
		for (int i = 0;i < n;i++) {
			if (tmp[i] == c) {
				cnt++;
			} else {
				if (same(c, tmp[i])) cnt++;
				if (cnt > n/2) return -R;
			}
		}
		return R;
	}
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:64:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   64 |  int siz = ws.size();
      |            ~~~~~~~^~
towns.cpp:68:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   68 |   int ind = lower_bound(ws.begin(), ws.end(), w[i]) - ws.begin();
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
towns.cpp:71:54: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   71 |  for (int i = 0;i < siz;i++) pref[i] = col[i].size() + (i ? pref[i-1] : 0);
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
towns.cpp:72:56: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   72 |  for (int i = siz-1;i >= 0;i--) suf[i] = col[i].size() + (i < siz-1 ? suf[i+1] : 0);
      |                                          ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:78:89: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |    if ((i == 0 || pref[i-1] <= n/2) && (i == siz-1 || suf[i+1] <= n/2) && col[i].size() <= n/2) {
      |                                                                           ~~~~~~~~~~~~~~^~~~~~
towns.cpp:80:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |    } else if (col[i].size() > n/2) {
      |               ~~~~~~~~~~~~~~^~~~~
towns.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int j = 0;j < n - col[i].size();j++) vec.push_back(n+j);
      |                    ~~^~~~~~~~~~~~~~~~~~~
towns.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (int i = 0;i < vec.size();i += 2) {
      |                  ~~^~~~~~~~~~~~
towns.cpp:108:16: warning: unused variable 'bad' [-Wunused-variable]
  108 |   int cnt = 1, bad = 0;
      |                ^~~
towns.cpp:33:28: warning: unused parameter 'sub' [-Wunused-parameter]
   33 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39