Submission #758749

#	Time	Username	Problem	Language	Result	Execution time	Memory
758749		SanguineChameleon	Saveit (IOI10_saveit)	C++17	100 / 100	147 ms	10624 KiB

encoder

#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>
using namespace std;

namespace encoder {
	const int maxn = 1e3 + 20;
	const int maxh = 40;
	vector<int> adj[maxn];
	int dist[maxh][maxn];
	bool flag[maxn];
	int par[maxn];
	long long diff[maxn];
	int n, h;

	void bfs(int s) {
		for (int i = 1; i <= n; i++) {
			dist[s][i] = -1;
		}
		dist[s][s] = 0;
		deque<int> q;
		q.push_back(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop_front();
			for (auto v: adj[u]) {
				if (dist[s][v] == -1) {
					dist[s][v] = dist[s][u] + 1;
					q.push_back(v);
				}
			}
		}
	}

	void dfs(int u) {
		flag[u] = true;
		for (auto v: adj[u]) {
			if (!flag[v]) {
				diff[v] = 0;
				for (int i = 1; i <= h; i++) {
					diff[v] = diff[v] * 3 + (dist[i][v] - dist[i][u] + 1);
				}
				par[v] = u;
				dfs(v);
			}
		}
	}
}

void encode(int n, int h, int m, int *x, int *y){
	encoder::n = n;
	encoder::h = h;
	for (int i = 0; i < m; i++) {
		int u = x[i] + 1;
		int v = y[i] + 1;
		encoder::adj[u].push_back(v);
		encoder::adj[v].push_back(u);
	}
	for (int i = 1; i <= h; i++) {
		encoder::bfs(i);
	}
	encoder::dfs(1);
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			encode_bit((encoder::par[i] >> j) & 1);
		}
		for (int j = 0; j < 58; j++) {
			encode_bit((encoder::diff[i] >> j) & 1);
		}
	}
}

decoder

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>
using namespace std;

namespace decoder {
	const int maxn = 1e3 + 20;
	const int maxh = 40;
	long long diff[maxn];
	int dist[maxh][maxn];
	vector<int> ch[maxn];
	int n, h;

	void dfs(int u) {
		for (auto v: ch[u]) {
			for (int i = h; i >= 1; i--) {
				dist[i][v] = dist[i][u] + (diff[v] % 3 - 1);
				diff[v] /= 3;
			}
			dfs(v);
		}
	}
}

void decode(int n, int h) {
	decoder::n = n;
	decoder::h = h;
	for (int i = 2; i <= n; i++) {
		int par = 0;
		for (int j = 0; j < 10; j++) {
			par |= decode_bit() << j;
		}
		decoder::ch[par].push_back(i);
		for (int j = 0; j < 58; j++) {
			decoder::diff[i] |= (long long)decode_bit() << j;
		}
	}
	decoder::dfs(1);
	for (int i = 1; i <= h; i++) {
		int off = n;
		for (int j = 1; j <= n; j++) {
			off = min(off, decoder::dist[i][j]);
		}
		for (int j = 1; j <= n; j++) {
			hops(i - 1, j - 1, decoder::dist[i][j] - off);
		}
	}
}

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