oj.uz

답안 #24753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24753 2017-06-13T00:03:56 Z Bruteforceman 저장 (Saveit) (IOI10_saveit) C++11
100 / 100
 335 ms 12296 KB 
#include "grader.h"
#include "encoder.h"
#include "bits/stdc++.h"
using namespace std;
vector <int> g[1005];
int dis[40][1005];
int par[1005];
vector <int> tree[1005];

void send_bit(int n, int bit) {
	// if(bit == 2) printf("sends in %d\n", n);
	for(int i = 0; i < bit; i++) {
		encode_bit((n >> i) & 1);
	}
}
void dfs(int x) {
	for(auto i : g[x]) {
		if(par[i] == -1) {
			par[i] = x;
			dfs(i);
		}
	}
}
void trav(int x) {
	for(auto i : tree[x]) {
		if(par[i] == -1) {
			par[i] = x;
			trav(i);
		}
	}
}
void shortest_path(int root) {
	queue <int> Q;
	Q.push(root);
	dis[root][root] = 0;
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		for(auto i : g[x]) {
			if(dis[root][i] == -1) {
				dis[root][i] = 1 + dis[root][x];
				Q.push(i);
			}
		}
	}
}

pair <int, int> cnt[3];

void send_shit(int x) {
	int pos = 0;
	for(int i = 0; i < 3; i++) {
		if(cnt[i].second == x) pos = i; 
	}	
	if(pos == 0) {
		encode_bit(0);
	} else if (pos == 1) {
		encode_bit(1);
		encode_bit(0);
	} else {
		encode_bit(1);
		encode_bit(1);
	}
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
	for(int i = 0; i < nv; i++) {
		g[i].clear();
		tree[i].clear();
	}
	memset(par, -1, sizeof par);
	memset(dis, -1, sizeof dis);

	for(int i = 0; i < ne; i++) {
		g[v1[i]].push_back(v2[i]);
		g[v2[i]].push_back(v1[i]);
	}
	par[0] = 0;
	dfs(0);
	for(int i = 1; i < nv; i++) {
		tree[par[i]].push_back(i);
		tree[i].push_back(par[i]);
		send_bit(par[i], 10);
	}
	vector <int> code;
	for(int i = 0; i < nh; i++) {
		shortest_path(i);
		memset(par, -1, sizeof par);
		par[i] = i; 
		trav(i);
		for(int j = 0; j < nv; j++) {
			if(j == i) continue;
			int dx = dis[i][j] - dis[i][par[j]];
			code.push_back(dx);
		}
	}
	cnt[0].second = 0;
	cnt[1].second = 1;
	cnt[2].second = 2;
	cnt[0].first = cnt[1].first = cnt[2].first = 0;
	for(auto i : code) {
		if(i == 0) cnt[0].first++;
		else if(i == 1) cnt[1].first++;
		else cnt[2].first++;
	}
	sort(cnt, cnt + 3);
	reverse(cnt, cnt + 3);

	send_bit(cnt[0].second, 2);
	send_bit(cnt[1].second, 2);
	send_bit(cnt[2].second, 2);

	for(auto i : code) {
		if(i == 0) send_shit(0);
		else if (i == 1) send_shit(1);
		else send_shit(2);
	}
	return;
}

#include "grader.h"
#include "decoder.h"
#include "bits/stdc++.h"
using namespace std;

#define ffs stfu

vector <int> v[1005];
int anc[1005];
int diff[1005];

int get_bit(int bit) {
	int ans = 0;
	for(int i = 0; i < bit; i++) {
		if(decode_bit()) ans |= 1 << i;
	}
	return ans;
}

void ffs(int x) {
	for(auto i : v[x]) {
		if(anc[i] == -1) {
			anc[i] = x;
			ffs(i);
		}
	}
}
void go(int x, int from, int root, int dist) {
	if(from != -1) {
		dist += diff[x];
	} 
	hops(root, x, dist);
	for(auto i : v[x]) {
		if(i != from) {
			go(i, x, root, dist);
		}
	} 
}
int dc[3];
int get_shit() {
	if(decode_bit()) {
		if(decode_bit()) return dc[2];
		else return dc[1];
	} else {
		return dc[0];
	}
}

void decode(int nv, int nh) {
	for(int i = 1; i < nv; i++) {
		int nd = get_bit(10);
		v[nd].push_back(i);
		v[i].push_back(nd);
	}
	dc[0] = get_bit(2);
	dc[1] = get_bit(2);
	dc[2] = get_bit(2);

	for(int i = 0; i < nh; i++) {
		memset(anc, -1, sizeof anc);
		anc[i] = i;
		diff[i] = 0;
		ffs(i);
		for(int j = 0; j < nv; j++) {
			if(i == j) continue;
			int num = get_shit();	
			if(num == 0) diff[j] = 0;
			else if (num == 1) diff[j] = 1;
			else diff[j] = -1;
		}	
		go(i, -1, i, 0);
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 12296 KB Output is correct - 63894 call(s) of encode_bit()
2 Correct 7 ms 5056 KB Output is correct - 62 call(s) of encode_bit()
3 Correct 31 ms 5872 KB Output is correct - 60446 call(s) of encode_bit()
4 Correct 6 ms 4976 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 34 ms 5900 KB Output is correct - 57371 call(s) of encode_bit()
6 Correct 39 ms 6064 KB Output is correct - 62208 call(s) of encode_bit()
7 Correct 65 ms 6528 KB Output is correct - 52281 call(s) of encode_bit()
8 Correct 32 ms 5928 KB Output is correct - 60553 call(s) of encode_bit()
9 Correct 28 ms 5800 KB Output is correct - 48562 call(s) of encode_bit()
10 Correct 33 ms 5856 KB Output is correct - 48564 call(s) of encode_bit()
11 Correct 57 ms 5904 KB Output is correct - 51297 call(s) of encode_bit()
12 Correct 26 ms 5844 KB Output is correct - 45960 call(s) of encode_bit()
13 Correct 73 ms 6620 KB Output is correct - 59069 call(s) of encode_bit()
14 Correct 30 ms 5984 KB Output is correct - 56269 call(s) of encode_bit()
15 Correct 35 ms 5984 KB Output is correct - 58047 call(s) of encode_bit()
16 Correct 75 ms 6496 KB Output is correct - 62373 call(s) of encode_bit()
17 Correct 68 ms 6496 KB Output is correct - 62348 call(s) of encode_bit()
18 Correct 85 ms 6832 KB Output is correct - 68114 call(s) of encode_bit()
19 Correct 46 ms 6328 KB Output is correct - 62763 call(s) of encode_bit()
20 Correct 108 ms 7032 KB Output is correct - 62995 call(s) of encode_bit()
21 Correct 101 ms 7084 KB Output is correct - 63458 call(s) of encode_bit()
22 Correct 78 ms 6540 KB Output is correct - 54298 call(s) of encode_bit()
23 Correct 106 ms 7208 KB Output is correct - 57581 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 12296 KB Output is correct - 63894 call(s) of encode_bit()
2 Correct 7 ms 5056 KB Output is correct - 62 call(s) of encode_bit()
3 Correct 31 ms 5872 KB Output is correct - 60446 call(s) of encode_bit()
4 Correct 6 ms 4976 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 34 ms 5900 KB Output is correct - 57371 call(s) of encode_bit()
6 Correct 39 ms 6064 KB Output is correct - 62208 call(s) of encode_bit()
7 Correct 65 ms 6528 KB Output is correct - 52281 call(s) of encode_bit()
8 Correct 32 ms 5928 KB Output is correct - 60553 call(s) of encode_bit()
9 Correct 28 ms 5800 KB Output is correct - 48562 call(s) of encode_bit()
10 Correct 33 ms 5856 KB Output is correct - 48564 call(s) of encode_bit()
11 Correct 57 ms 5904 KB Output is correct - 51297 call(s) of encode_bit()
12 Correct 26 ms 5844 KB Output is correct - 45960 call(s) of encode_bit()
13 Correct 73 ms 6620 KB Output is correct - 59069 call(s) of encode_bit()
14 Correct 30 ms 5984 KB Output is correct - 56269 call(s) of encode_bit()
15 Correct 35 ms 5984 KB Output is correct - 58047 call(s) of encode_bit()
16 Correct 75 ms 6496 KB Output is correct - 62373 call(s) of encode_bit()
17 Correct 68 ms 6496 KB Output is correct - 62348 call(s) of encode_bit()
18 Correct 85 ms 6832 KB Output is correct - 68114 call(s) of encode_bit()
19 Correct 46 ms 6328 KB Output is correct - 62763 call(s) of encode_bit()
20 Correct 108 ms 7032 KB Output is correct - 62995 call(s) of encode_bit()
21 Correct 101 ms 7084 KB Output is correct - 63458 call(s) of encode_bit()
22 Correct 78 ms 6540 KB Output is correct - 54298 call(s) of encode_bit()
23 Correct 106 ms 7208 KB Output is correct - 57581 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 12296 KB Output is correct - 63894 call(s) of encode_bit()
2 Correct 7 ms 5056 KB Output is correct - 62 call(s) of encode_bit()
3 Correct 31 ms 5872 KB Output is correct - 60446 call(s) of encode_bit()
4 Correct 6 ms 4976 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 34 ms 5900 KB Output is correct - 57371 call(s) of encode_bit()
6 Correct 39 ms 6064 KB Output is correct - 62208 call(s) of encode_bit()
7 Correct 65 ms 6528 KB Output is correct - 52281 call(s) of encode_bit()
8 Correct 32 ms 5928 KB Output is correct - 60553 call(s) of encode_bit()
9 Correct 28 ms 5800 KB Output is correct - 48562 call(s) of encode_bit()
10 Correct 33 ms 5856 KB Output is correct - 48564 call(s) of encode_bit()
11 Correct 57 ms 5904 KB Output is correct - 51297 call(s) of encode_bit()
12 Correct 26 ms 5844 KB Output is correct - 45960 call(s) of encode_bit()
13 Correct 73 ms 6620 KB Output is correct - 59069 call(s) of encode_bit()
14 Correct 30 ms 5984 KB Output is correct - 56269 call(s) of encode_bit()
15 Correct 35 ms 5984 KB Output is correct - 58047 call(s) of encode_bit()
16 Correct 75 ms 6496 KB Output is correct - 62373 call(s) of encode_bit()
17 Correct 68 ms 6496 KB Output is correct - 62348 call(s) of encode_bit()
18 Correct 85 ms 6832 KB Output is correct - 68114 call(s) of encode_bit()
19 Correct 46 ms 6328 KB Output is correct - 62763 call(s) of encode_bit()
20 Correct 108 ms 7032 KB Output is correct - 62995 call(s) of encode_bit()
21 Correct 101 ms 7084 KB Output is correct - 63458 call(s) of encode_bit()
22 Correct 78 ms 6540 KB Output is correct - 54298 call(s) of encode_bit()
23 Correct 106 ms 7208 KB Output is correct - 57581 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 335 ms 12296 KB Output is correct - 63894 call(s) of encode_bit()
2 Correct 7 ms 5056 KB Output is correct - 62 call(s) of encode_bit()
3 Correct 31 ms 5872 KB Output is correct - 60446 call(s) of encode_bit()
4 Correct 6 ms 4976 KB Output is correct - 76 call(s) of encode_bit()
5 Correct 34 ms 5900 KB Output is correct - 57371 call(s) of encode_bit()
6 Correct 39 ms 6064 KB Output is correct - 62208 call(s) of encode_bit()
7 Correct 65 ms 6528 KB Output is correct - 52281 call(s) of encode_bit()
8 Correct 32 ms 5928 KB Output is correct - 60553 call(s) of encode_bit()
9 Correct 28 ms 5800 KB Output is correct - 48562 call(s) of encode_bit()
10 Correct 33 ms 5856 KB Output is correct - 48564 call(s) of encode_bit()
11 Correct 57 ms 5904 KB Output is correct - 51297 call(s) of encode_bit()
12 Correct 26 ms 5844 KB Output is correct - 45960 call(s) of encode_bit()
13 Correct 73 ms 6620 KB Output is correct - 59069 call(s) of encode_bit()
14 Correct 30 ms 5984 KB Output is correct - 56269 call(s) of encode_bit()
15 Correct 35 ms 5984 KB Output is correct - 58047 call(s) of encode_bit()
16 Correct 75 ms 6496 KB Output is correct - 62373 call(s) of encode_bit()
17 Correct 68 ms 6496 KB Output is correct - 62348 call(s) of encode_bit()
18 Correct 85 ms 6832 KB Output is correct - 68114 call(s) of encode_bit()
19 Correct 46 ms 6328 KB Output is correct - 62763 call(s) of encode_bit()
20 Correct 108 ms 7032 KB Output is correct - 62995 call(s) of encode_bit()
21 Correct 101 ms 7084 KB Output is correct - 63458 call(s) of encode_bit()
22 Correct 78 ms 6540 KB Output is correct - 54298 call(s) of encode_bit()
23 Correct 106 ms 7208 KB Output is correct - 57581 call(s) of encode_bit()