oj.uz

답안 #45129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45129 2018-04-11T12:09:33 Z tjd229 저장 (Saveit) (IOI10_saveit) C++11
100 / 100
 276 ms 13656 KB 
#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;
		}
	}
}
#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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 13656 KB Output is correct - 65878 call(s) of encode_bit()
2 Correct 7 ms 4808 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 32 ms 10408 KB Output is correct - 59278 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 64 call(s) of encode_bit()
5 Correct 39 ms 9840 KB Output is correct - 59278 call(s) of encode_bit()
6 Correct 37 ms 10324 KB Output is correct - 65878 call(s) of encode_bit()
7 Correct 82 ms 10272 KB Output is correct - 65878 call(s) of encode_bit()
8 Correct 35 ms 12912 KB Output is correct - 63304 call(s) of encode_bit()
9 Correct 37 ms 13168 KB Output is correct - 65878 call(s) of encode_bit()
10 Correct 38 ms 13248 KB Output is correct - 65878 call(s) of encode_bit()
11 Correct 38 ms 12824 KB Output is correct - 65878 call(s) of encode_bit()
12 Correct 36 ms 13568 KB Output is correct - 65878 call(s) of encode_bit()
13 Correct 72 ms 10800 KB Output is correct - 65878 call(s) of encode_bit()
14 Correct 38 ms 12940 KB Output is correct - 65878 call(s) of encode_bit()
15 Correct 39 ms 13208 KB Output is correct - 65878 call(s) of encode_bit()
16 Correct 83 ms 12488 KB Output is correct - 65878 call(s) of encode_bit()
17 Correct 66 ms 12716 KB Output is correct - 65878 call(s) of encode_bit()
18 Correct 85 ms 11900 KB Output is correct - 65878 call(s) of encode_bit()
19 Correct 52 ms 11760 KB Output is correct - 65878 call(s) of encode_bit()
20 Correct 97 ms 11244 KB Output is correct - 65878 call(s) of encode_bit()
21 Correct 114 ms 11376 KB Output is correct - 65878 call(s) of encode_bit()
22 Correct 61 ms 10592 KB Output is correct - 65878 call(s) of encode_bit()
23 Correct 108 ms 10848 KB Output is correct - 65878 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 13656 KB Output is correct - 65878 call(s) of encode_bit()
2 Correct 7 ms 4808 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 32 ms 10408 KB Output is correct - 59278 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 64 call(s) of encode_bit()
5 Correct 39 ms 9840 KB Output is correct - 59278 call(s) of encode_bit()
6 Correct 37 ms 10324 KB Output is correct - 65878 call(s) of encode_bit()
7 Correct 82 ms 10272 KB Output is correct - 65878 call(s) of encode_bit()
8 Correct 35 ms 12912 KB Output is correct - 63304 call(s) of encode_bit()
9 Correct 37 ms 13168 KB Output is correct - 65878 call(s) of encode_bit()
10 Correct 38 ms 13248 KB Output is correct - 65878 call(s) of encode_bit()
11 Correct 38 ms 12824 KB Output is correct - 65878 call(s) of encode_bit()
12 Correct 36 ms 13568 KB Output is correct - 65878 call(s) of encode_bit()
13 Correct 72 ms 10800 KB Output is correct - 65878 call(s) of encode_bit()
14 Correct 38 ms 12940 KB Output is correct - 65878 call(s) of encode_bit()
15 Correct 39 ms 13208 KB Output is correct - 65878 call(s) of encode_bit()
16 Correct 83 ms 12488 KB Output is correct - 65878 call(s) of encode_bit()
17 Correct 66 ms 12716 KB Output is correct - 65878 call(s) of encode_bit()
18 Correct 85 ms 11900 KB Output is correct - 65878 call(s) of encode_bit()
19 Correct 52 ms 11760 KB Output is correct - 65878 call(s) of encode_bit()
20 Correct 97 ms 11244 KB Output is correct - 65878 call(s) of encode_bit()
21 Correct 114 ms 11376 KB Output is correct - 65878 call(s) of encode_bit()
22 Correct 61 ms 10592 KB Output is correct - 65878 call(s) of encode_bit()
23 Correct 108 ms 10848 KB Output is correct - 65878 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 13656 KB Output is correct - 65878 call(s) of encode_bit()
2 Correct 7 ms 4808 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 32 ms 10408 KB Output is correct - 59278 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 64 call(s) of encode_bit()
5 Correct 39 ms 9840 KB Output is correct - 59278 call(s) of encode_bit()
6 Correct 37 ms 10324 KB Output is correct - 65878 call(s) of encode_bit()
7 Correct 82 ms 10272 KB Output is correct - 65878 call(s) of encode_bit()
8 Correct 35 ms 12912 KB Output is correct - 63304 call(s) of encode_bit()
9 Correct 37 ms 13168 KB Output is correct - 65878 call(s) of encode_bit()
10 Correct 38 ms 13248 KB Output is correct - 65878 call(s) of encode_bit()
11 Correct 38 ms 12824 KB Output is correct - 65878 call(s) of encode_bit()
12 Correct 36 ms 13568 KB Output is correct - 65878 call(s) of encode_bit()
13 Correct 72 ms 10800 KB Output is correct - 65878 call(s) of encode_bit()
14 Correct 38 ms 12940 KB Output is correct - 65878 call(s) of encode_bit()
15 Correct 39 ms 13208 KB Output is correct - 65878 call(s) of encode_bit()
16 Correct 83 ms 12488 KB Output is correct - 65878 call(s) of encode_bit()
17 Correct 66 ms 12716 KB Output is correct - 65878 call(s) of encode_bit()
18 Correct 85 ms 11900 KB Output is correct - 65878 call(s) of encode_bit()
19 Correct 52 ms 11760 KB Output is correct - 65878 call(s) of encode_bit()
20 Correct 97 ms 11244 KB Output is correct - 65878 call(s) of encode_bit()
21 Correct 114 ms 11376 KB Output is correct - 65878 call(s) of encode_bit()
22 Correct 61 ms 10592 KB Output is correct - 65878 call(s) of encode_bit()
23 Correct 108 ms 10848 KB Output is correct - 65878 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 13656 KB Output is correct - 65878 call(s) of encode_bit()
2 Correct 7 ms 4808 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 32 ms 10408 KB Output is correct - 59278 call(s) of encode_bit()
4 Correct 7 ms 4976 KB Output is correct - 64 call(s) of encode_bit()
5 Correct 39 ms 9840 KB Output is correct - 59278 call(s) of encode_bit()
6 Correct 37 ms 10324 KB Output is correct - 65878 call(s) of encode_bit()
7 Correct 82 ms 10272 KB Output is correct - 65878 call(s) of encode_bit()
8 Correct 35 ms 12912 KB Output is correct - 63304 call(s) of encode_bit()
9 Correct 37 ms 13168 KB Output is correct - 65878 call(s) of encode_bit()
10 Correct 38 ms 13248 KB Output is correct - 65878 call(s) of encode_bit()
11 Correct 38 ms 12824 KB Output is correct - 65878 call(s) of encode_bit()
12 Correct 36 ms 13568 KB Output is correct - 65878 call(s) of encode_bit()
13 Correct 72 ms 10800 KB Output is correct - 65878 call(s) of encode_bit()
14 Correct 38 ms 12940 KB Output is correct - 65878 call(s) of encode_bit()
15 Correct 39 ms 13208 KB Output is correct - 65878 call(s) of encode_bit()
16 Correct 83 ms 12488 KB Output is correct - 65878 call(s) of encode_bit()
17 Correct 66 ms 12716 KB Output is correct - 65878 call(s) of encode_bit()
18 Correct 85 ms 11900 KB Output is correct - 65878 call(s) of encode_bit()
19 Correct 52 ms 11760 KB Output is correct - 65878 call(s) of encode_bit()
20 Correct 97 ms 11244 KB Output is correct - 65878 call(s) of encode_bit()
21 Correct 114 ms 11376 KB Output is correct - 65878 call(s) of encode_bit()
22 Correct 61 ms 10592 KB Output is correct - 65878 call(s) of encode_bit()
23 Correct 108 ms 10848 KB Output is correct - 65878 call(s) of encode_bit()