Submission #24752

#	Time	Username	Problem	Language	Result	Execution time	Memory
24752		Bruteforceman	Saveit (IOI10_saveit)	C++11	50 / 100	289 ms	12240 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);
			}
		}
	}
}

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);
		}
	}
	for(auto i : code) {
		if(i == 0) send_bit(0, 2);
		else if(i == 1) send_bit(1, 2);
		else send_bit(2, 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);
		}
	} 
}
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);
	}
	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_bit(2);			
			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: 0 / 25
• Subtask 4: 0 / 25