Submission #45124

#	Time	Username	Problem	Language	Result	Execution time	Memory
45124		tjd229	Saveit (IOI10_saveit)	C++11	0 / 100	223 ms	13696 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <stdio.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;
	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;
		}
	}
	for (i = 1; i < nv; i++){
		v = q[i];
		for (j = 1; j < nh; j++){
			if (i == j) continue;
			int d = dist[j][v] - dist[j][p[v]] + 1;
			encode_bit(d & 1);
			encode_bit((d>>1) & 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 << k);
		}
		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];
	for (i = 1; i < nv; i++){
		int v = que[i];
		for (j = 1; j < nh; j++){
			if (i == j) continue;
			int rd = decode_bit();
			int b = decode_bit();
			rd += (b << 1)-1;
			dist[j][v] = dist[j][par[v]] + rd;
		}
	}

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

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:57:12: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
    p += (b << k);
         ~~~^~~~~

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