제출 #45129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45129		tjd229	저장 (Saveit) (IOI10_saveit)	C++11	100 / 100	276 ms	13656 KiB

encoder

#include "grader.h"
#include "encoder.h"
int p[1000];
int visit[1000];
int edge[1000][1000];
int tail[1000];
int dist[36][1000];
int q[1000];
int front;
int back;
void bfs(int nv, int src){
	visit[src] = src + 1;
	dist[src][src] = 0;
	front = back = 0;
	q[back++] = src;
	int i;

	while (front != back){
		int curr = q[front++];
		for (i = 0; i < tail[curr]; i++){
			int nxt = edge[curr][i];
			if (visit[nxt] != src + 1){
				visit[nxt] = src + 1;
				q[back++] = nxt;
				p[nxt] = curr;
				dist[src][nxt] = dist[src][curr] + 1;
			}
		}
	}
}

void cnt_sort(int len, int *li){
	int cnt[1001] = { 0 };
	int i, j;
	for (i = 0; i < len; i++) cnt[li[i]]++;
	for (i = 1000, j = len; i >= 0; i--){
		while (cnt[i]--) li[--j] = i;
	}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
	int i, j;
	int u, v;
	int buf[36 * 1000] = { 0 };
	while (ne--){
		u = v1[ne];
		v = v2[ne];
		edge[u][tail[u]++] = v;
		edge[v][tail[v]++] = u;
	}
	for (i = 0; i < nv; i++) cnt_sort(tail[i], edge[i]);
	for (i = nh; i--;){
		bfs(nv, i);
	}
	for (i = 1; i < nv; i++){		//for 0
		u = p[i];
		j = 10;
		while (j--){
			encode_bit(u & 1);
			u >>= 1;
		}
	}
	tail[0] = 0;
	for (i = 1; i < nv; i++){
		v = q[i];
		for (j = 1; j < nh; j++){
			if (v == j) continue;
			int d = dist[j][v] - dist[j][p[v]] + 1;
			buf[tail[0]++] = d;
			//encode_bit(d & 1);
			//encode_bit((d >> 1) & 1);
		}
	}
	for (i = 0; i < tail[0]; ){
		int f = 0;
		for (j = 0; j < 5; j++,i++){
			f = f * 3 + buf[i];
		}
		for (j = 0; j < 8; j++){
			encode_bit(f & 1);
			f >>= 1;
		}
	}
}

decoder

#include "grader.h"
#include "decoder.h"

int tmp[1000];
int par[1000];
int que[1000];

void msort(int s, int e, int *li){
	if (s >= e) return;
	int m = (s + e) >> 1;
	msort(s, m, li);
	msort(m + 1, e, li);
	int i, l, r;
	l = s;
	r = m + 1;
	for (i = s; i <= e; i++){
		if (l > m) tmp[i] = li[r++];
		else if (r > e) tmp[i] = li[l++];
		else{
			tmp[i] = li[l] < li[r] ? li[l++] : li[r++];
		}
	}
	for (i = s; i <= e; i++) li[i] = tmp[i];
}
void bfs0(int nv, int *dist, int *tail, int edge[1000][1000]){
	bool visit[1000] = { 0 };
	int front, back;
	visit[0] = 1;
	dist[0] = 0;
	front = back = 0;
	que[back++] = 0;
	int i;

	while (front != back){
		int curr = que[front++];
		for (i = 0; i < tail[curr]; i++){
			int nxt = edge[curr][i];
			if (!visit[nxt]){
				visit[nxt] = 1;
				que[back++] = nxt;
				par[nxt] = curr;
				dist[nxt] = dist[curr] + 1;
			}
		}
	}
}
void decode(int nv, int nh) {
	int i, j, k;
	int edge[1000][1000];
	int tail[1000] = { 0 };
	int dist[36][1000] = { 0 };
	for (i = 1; i < nv; i++){
		int p = 0;
		for (j = 0; j < 10; j++){
			int b = decode_bit();
			p += (b << j);
		}
		edge[p][tail[p]++] = i;
	}
	for (i = 0; i < nv; i++) msort(0, tail[i] - 1, edge[i]);
	bfs0(nv, dist[0], tail, edge);
	for (i = 1; i < nh; i++) dist[i][0] = dist[0][i];
	int div = 0;
	int f;
	for (i = 1; i < nv; i++){
		int v = que[i];
		for (j = 1; j < nh; j++){
			if (v == j) continue;
			if (div == 0){
				div = 3 * 3 * 3 * 3;
				f = 0;
				for (k = 0; k < 8; k++){
					int b = decode_bit();
					f += (b << k);
				}
			}
			int rd = f / div;
			f %= div;
			div /= 3;

			dist[j][v] = dist[j][par[v]] + rd - 1;
		}
	}

	for (i = 0; i < nh; i++) for (j = 0; j < nv; j++) hops(i, j, dist[i][j]);

}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25