IOI 2010 Saveit

관찰 1. 간선으로 이웃한 정점은 허브와의 거리가 최대 1 차이 난다.

관찰 2. 스패닝 트리를 만들면 모든 정점에서 허브 i까지의 거리를 N-1개의 -1에서 1 사이의 정수로 표현할 수 있다. i에서 i까지의 거리는 0이라고 알 수 있고, dfs를 통해 거리를 계산해 줄 수 있기 때문이다.

이를 통하면 최적의 전략은 스패닝 트리와 간선에 대한 정보를 보내주고, 그것을 통해서 계산하는 것임을 알 수 있다. 스패닝 트리는 각 정점의 부모를 저장하면 9990 비트로 보낼 수 있다. 거리는 이론상 999*36*log 3개의 비트로 나타낼 수 있고, 실제로는 5개의 정수를 그룹지은 뒤 이를 8개의 비트로 나타내어 보냈다. 이는 57600비트를 사용하고, 이를 통해 만점을 받을 수 있다.

#include "grader.h"
#include "decoder.h"
#include "encoder.h"
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
vector<int>link[1010];
vector<int>link2[1010];
int uf[1010];
int f(int n)
{
	return uf[n] == n ? n : uf[n] = f(uf[n]);
}
int u(int n, int m)
{
	n = f(n);
	m = f(m);
	if (n == m)
		return 0;
	uf[n] = uf[m];
	return 1;
}
int arr[1010];
void dfs(int n,int p)
{
	arr[n] = p;
	int i;
	for (i = 0; i < link[n].size(); i++)
	{
		if (link[n][i] != p)
		{
			dfs(link[n][i], n);
		}
	}
}
int arr2[1010];
void sssp(int n)
{
	memset(arr2, -1, sizeof(arr2));
	queue<int>q;
	q.push(n);
	arr2[n] = 0;
	while (q.size())
	{
		int t = q.front();
		q.pop();
		int j;
		for (j = 0; j < link2[t].size(); j++)
		{
			if (arr2[link2[t][j]]==-1)
			{
				arr2[link2[t][j]] = arr2[t] + 1;
				q.push(link2[t][j]);
			}
		}
	}
}
void encode(int nv, int nh, int ne, int* v1, int* v2) 
{
	int i;
	for (i = 0; i < nv; i++)
		uf[i] = i;
	for (i = 0; i < ne; i++)
	{
		if (u(v1[i], v2[i]))
		{
			link[v1[i]].push_back(v2[i]);
			link[v2[i]].push_back(v1[i]);
		}
		link2[v1[i]].push_back(v2[i]);
		link2[v2[i]].push_back(v1[i]);
	}
	dfs(0, 0);
	for (i = 1; i < nv; i++)
	{
		int j;
		for (j = 0; j < 10; j++)
		{
			encode_bit(!(!(arr[i] & (1 << j))));
		}
	}
	vector<int>x;
	for (i = 0; i < nh; i++)
	{
		sssp(i);
		int j;
		
		for (j = 1; j < nv; j++)
		{
			x.push_back(arr2[arr[j]] - arr2[j]);
		}
	}
	while (x.size() % 5)
	{
		x.push_back(0);
	}
	for (i = 0; i < x.size();i+=5)
	{
		int v = 0;
		int c = 1;
		int j;
		for (j = 0; j < 5; j++)
		{
			v += c * (x[i + j] + 1); c *= 3;
		}
		for (j = 0; j < 8; j++)
		{
			encode_bit(!(!(v & (1 << j))));
		}
	}
}
vector<pair<int,int>>link3[1010];
int didiff[40][1010];
int bef[1010];
int res[1010];
void dfs2(int n, int p,int r)
{
	res[n] = r;
	int i;
	for (i = 0; i < link3[n].size(); i++)
	{
		if (link3[n][i].first != p)
		{
			dfs2(link3[n][i].first, n,r+link3[n][i].second);
		}
	}
}
void decode(int nv, int nh) 
{
	int siz = ((nv - 1) * nh + 4) / 5*5;
	int i;
	for (i = 1; i < nv; i++)
	{
		int v = 0;
		int j;
		for (j = 0; j < 10; j++)
		{
			v += decode_bit() << j;
		}
		bef[i] = v;
	}
	int c1 = 0;
	int c2 = 1;
	for (i =0; i < siz; i+=5)
	{
		int v = 0;
		int j;
		for (j = 0; j < 8; j++)
		{
			v += decode_bit() << j;
		}
		int c = 1;
		for (j = 0; j < 5; j++)
		{
			didiff[c1][c2] = ((v / c) % 3-1);
			c *=3;
			c2++;
			if (c2 == nv)
			{
				c1++;
				c2 = 1;
			}
		}
	}
	for (i = 0; i < nh; i++)
	{
		int j;
		for (j = 1; j < nv; j++)
		{
			link3[j].push_back({ bef[j],didiff[i][j] });
			link3[bef[j]].push_back({ j,-didiff[i][j] });
		}
		dfs2(i, -1, 0);
		for (j = 0; j < nv; j++)
		{
			hops(i, j, res[j]);
			link3[j].clear();
		}
	}
}