Submission #24753

#	Time	Username	Problem	Language	Result	Execution time	Memory
24753		Bruteforceman	Saveit (IOI10_saveit)	C++11	100 / 100	335 ms	12296 KiB

encoder

#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;
}

decoder

#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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25