oj.uz

Submission #46253

# Submission time Handle Problem Language Result Execution time Memory
46253 2018-04-18T09:29:14 Z RayaBurong25_1 Towns (IOI15_towns) C++14
25 / 100
 61 ms 4008 KB 
#include "towns.h"
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <cassert>
int Dist[111][111];
int X[111];
int L[111] = {0}, Ln[111] = {0};
int M[111] = {0}, Mn[111] = {0};
int R[111] = {0}, Rn[111] = {0};
std::map<int, std::vector<std::pair<int, int> > > Map;
int calcMn(std::vector<std::pair<int, int> > V)
{
	int In[111] = {0};
	int Cnt, Max = 0;
	int i, j;
	for (i = 0; i < V.size(); i++)
	{
		if (!In[i])
		{
			Cnt = 1;
			In[i] = 1;
			for (j = 0; j < V.size(); j++)
			{
				if (!In[j] && getDistance(V[i].second, V[j].second) < V[i].first + V[j].first)
				{
					In[j] = 1;
					Cnt++;
				}
			}
			if (Cnt > Max)
				Max = Cnt;
		}
	}
	return Max;
}
int hubDistance(int N, int sub)
{
	int i, j;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (i == j)
				Dist[i][j] = 0;
			else
				Dist[i][j] = -1;
		}
	}
	int u = 0;
	for (i = 0; i < N; i++)
	{
		if (Dist[0][i] == -1)
		{
			Dist[0][i] = getDistance(0, i);
			Dist[i][0] = Dist[0][i];
		}
		if (Dist[0][i] > Dist[0][u])
			u = i;
	}
	int v = u;
	for (i = 0; i < N; i++)
	{
		if (Dist[u][i] == -1)
		{
			Dist[u][i] = getDistance(u, i);
			Dist[i][u] = Dist[u][i];
		}
		if (Dist[u][i] > Dist[u][v])
			v = i;
	}
	for (i = 0; i < N; i++)
	{
		if (Dist[v][i] == -1)
		{
			Dist[v][i] = getDistance(v, i);
			Dist[i][v] = Dist[v][i];
		}
	}
	// printf("diameter %d-%d\n", u, v);
	int x, y;
	std::vector<std::pair<int, int> > emptyv(0);
	Map.clear();
	// assert(Map.empty());
	for (i = 0; i < N; i++)
	{
		y = (Dist[u][i] + Dist[i][v] - Dist[u][v])/2;
		x = Dist[u][i] - y;
		assert(x >= 0 && y >= 0);
		// printf("i%d x%d y%d\n", i, x, y);
		if (Map.find(x) == Map.end())
		{
			Map.insert({x, emptyv});
		}
		Map[x].push_back({y, i});
	}
	int Ans = 1000000007, Hub = 0;
	std::map<int, std::vector<std::pair<int, int> > >::iterator it;
	for (it = Map.begin(), i = 0; it != Map.end(); it++, i++)
	{
		X[i] = it->first;
		assert(X[i] >= 0 && X[i] <= Dist[u][v]);
		Mn[i] = it->second.size();
		if (i > 0)
		{
			L[i] = std::max(L[i - 1], M[i - 1]) + (X[i] - X[i - 1]);
			Ln[i] = Ln[i - 1] + Mn[i - 1];
		}
		else
		{
			L[i] = 0;
			Ln[i] = 0;
		}
		M[i] = 0;
		for (j = 0; j < it->second.size(); j++)
			M[i] = std::max(M[i], it->second[j].first);
	}
	int l = i;
	it--;
	for (i = l - 1; i >= 0; i--, it--)
	{
		if (i < l - 1)
		{
			R[i] = std::max(R[i + 1], M[i + 1]) + (X[i + 1] - X[i]);
			Rn[i] = Rn[i + 1] + Mn[i + 1];
		}
		else
		{
			R[i] = 0;
			Rn[i] = 0;
		}
		assert(L[i] >= 0 && L[i] <= Dist[u][v]);
		assert(M[i] >= 0 && M[i] <= Dist[u][v]);
		assert(R[i] >= 0 && R[i] <= Dist[u][v]);
		// printf("L%d M%d R%d\n", L[i], M[i], R[i]);
		if (std::max(std::max(L[i], M[i]), R[i]) <= Ans)
		{
			Ans = std::max(std::max(L[i], M[i]), R[i]);
			if (sub == 3)
			{
				Hub |= std::max(std::max(Ln[i], calcMn(it->second)), Rn[i]) <= N/2;
			}
			else if (sub == 4)
			{
				Hub |= std::max(std::max(Ln[i], Mn[i]), Rn[i]) <= N/2;
			}
		}
	}
	// assert(Dist[u][v] != -1);
	// assert(Ans <= Dist[u][v]);
	if (Hub)
		return Ans;
	else
		return -Ans;
}

Compilation message

towns.cpp: In function 'int calcMn(std::vector<std::pair<int, int> >)':
towns.cpp:18:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < V.size(); i++)
              ~~^~~~~~~~~~
towns.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (j = 0; j < V.size(); j++)
                ~~^~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:104:26: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   Mn[i] = it->second.size();
           ~~~~~~~~~~~~~~~^~
towns.cpp:116:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < it->second.size(); j++)
               ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 376 KB Output is correct
2 Correct 61 ms 1028 KB Output is correct
3 Correct 2 ms 1028 KB Output is correct
4 Correct 23 ms 1580 KB Output is correct
5 Correct 22 ms 2180 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2180 KB Output is correct
2 Correct 16 ms 2656 KB Output is correct
3 Correct 31 ms 3316 KB Output is correct
4 Correct 22 ms 3832 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 3832 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 4008 KB Output isn't correct
2 Halted 0 ms 0 KB -