Submission #384248

#	Time	Username	Problem	Language	Result	Execution time	Memory
384248		luciocf	Towns (IOI15_towns)	C++14	35 / 100	25 ms	492 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"
 
using namespace std;
 
const int maxn = 120;
 
int n;
 
int du[maxn], d0[maxn];
 
int sobe[maxn], qual[maxn];
 
int nivel[maxn];

int dp[maxn][maxn];
 
vector<int> all;
 
bool check(int u, int v)
{
	if (dp[u][v] != -1) return dp[u][v];

	return dp[u][v] = getDistance(u, v) < nivel[u] + nivel[v];
}
 
int get_major(void)
{
	vector<int> lista, bucket;
 
	for (auto w: all)
	{
		if (!lista.size())
		{
			lista.push_back(w);
			continue;
		}
 
		if (check(w, lista.back())) bucket.push_back(w);
		else
		{
			lista.push_back(w);
 
			if (bucket.size())
			{
				lista.push_back(bucket.back());
				bucket.pop_back();
			}
		}
	}
 
	int T = lista.back();
	int cnt = 0;
 
	while (lista.size())
	{
		if (check(T, lista.back()))
		{
			cnt++;
			lista.pop_back();
			if (lista.size()) lista.pop_back();
		}
		else
		{
			lista.pop_back();
 
			if (!bucket.size()) return 0;
 
			cnt++;
			bucket.pop_back();
		}
	}
 
	return cnt + bucket.size();
}
 
int hubDistance(int N, int subtask)
{
	memset(dp, -1, sizeof dp);
	n = N;
	all.clear();
 
	int mx = 0, u = 1;
 
	for (int i = 1; i < n; i++)
	{
		d0[i] = getDistance(0, i);
 
		if (d0[i] > mx)
		{
			mx = d0[i];
			u = i;
		}
	}
 	
 	int diam = 0, v = 0;
 
	for (int i = 0; i < n; i++)
	{
		du[i] = getDistance(u, i);
 
		if (du[i] > diam)
		{
			diam = du[i];
			v = i;
		}
	}
 
	int best = 1e9+10;
 	int from;
 
	for (int i = 1; i < n; i++)
	{
		if (i != u)
		{
			int k = (du[i] + d0[i] - mx)/2;
 			
			best = min(best, max(du[i]-k, diam-(du[i]-k)));
 
			if (best == du[i]-k) from = u;
			else if (best == diam-(du[i]-k)) from = 0;
 
			if (du[i]-k <= diam-(du[i]-k))
			{
				sobe[i] = du[i]-k, qual[i] = u;
				nivel[i] = k;
			}
			else
			{
				sobe[i] = diam-(du[i]-k), qual[i] = 0;
				nivel[i] = du[i] - sobe[i];
			}
		}
	}
 
	int A = 0, B = 0;
 
	for (int i = 0; i < n; i++)
	{
		if (i == u) A++;
		else if (i == 0) B++;
		else if (sobe[i] == best || sobe[i] == diam-best) all.push_back(i);
		else if (qual[i] == u) A++;
		else B++;
	}
 
	if (max({A, B, get_major()}) <= n/2) return best;
 
	all.clear();
	A = B = 0;
 
	if (from == u)
	{
		int second = 0;
 
		for (int i = 1; i < n; i++)
		{
			if (i == u) continue;
 
			if (du[i]-nivel[i] < best) second = max(second, du[i]-nivel[i]);
		}
 
		if (second != diam-best) return -best;
 
		for (int i = 0; i < n; i++)
		{
			if (i == u) A++;
			else if (i == 0) B++;
			else if (du[i]-nivel[i] == second) all.push_back(i);
			else if (qual[i] == u) A++;
			else B++;
		}
 
		if (max({A, B, get_major()}) <= n/2) return best;
	}
	else
	{
		int second = 0;
 
		for (int i = 1; i < n; i++)
			if (d0[i]-nivel[i] < best)
				second = max(second, d0[i]-nivel[i]);
 
		if (second != diam-best) return -best;
 
		for (int i = 0; i < n; i++)
		{
			if (i == u) A++;
			else if (i == 0) B++;
			else if (d0[i]-nivel[i] == second) all.push_back(i);
			else if (qual[i] == u) A++;
			else B++;
		}
 
		if (max({A, B, get_major()}) <= n/2) return best;
	}
 
	return -best;
}

Compilation message (stderr)

towns.cpp: In function 'bool check(int, int)':
towns.cpp:24:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   24 |  return dp[u][v] = getDistance(u, v) < nivel[u] + nivel[v];
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp: In function 'int get_major()':
towns.cpp:74:13: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   74 |  return cnt + bucket.size();
      |         ~~~~^~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:96:17: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   96 |   int diam = 0, v = 0;
      |                 ^
towns.cpp:77:28: warning: unused parameter 'subtask' [-Wunused-parameter]
   77 | int hubDistance(int N, int subtask)
      |                        ~~~~^~~~~~~
towns.cpp:152:2: warning: 'from' may be used uninitialized in this function [-Wmaybe-uninitialized]
  152 |  if (from == u)
      |  ^~

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