제출 #46229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46229		RayaBurong25_1	도시들 (IOI15_towns)	C++17	컴파일 에러	0 ms	0 KiB

towns

#include "towns.h"
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <assert>
int Dist[111][111];
int X[111];
int L[111], Ln[111];
int M[111], Mn[111];
int R[111], Rn[111];
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);
	std::map<int, std::vector<std::pair<int, int> > > Map;
	int x, y;
	for (i = 0; i < N; i++)
	{
		y = (Dist[u][i] + Dist[i][v] - Dist[u][v])/2;
		x = Dist[u][i] - y;
		// printf("i%d x%d y%d\n", i, x, y);
		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;
		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] + M[i - 1];
		}
		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] + M[i + 1];
		}
		// 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(Ans != 1000000007);
	if (Hub)
		return Ans;
	else
		return -Ans;
}

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp:6:10: fatal error: assert: No such file or directory
 #include <assert>
          ^~~~~~~~
compilation terminated.