Submission #62654

#	Time	Username	Problem	Language	Result	Execution time	Memory
62654		aome	Saveit (IOI10_saveit)	C++17	100 / 100	438 ms	12520 KiB

encoder

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

#include <bits/stdc++.h>

using namespace std;

static const int M = 36;
static const int N = 1000;

static int par[N];
static int dis[M][N];
static vector<int> G[N];

static void dfs(int u) {
	for (auto v : G[u]) {
		if (par[v] == -1) par[v] = u, dfs(v);
	}
}

static void bfs(int r) {
	queue<int> qu;
	qu.push(r), dis[r][r] = 0;
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto v : G[u]) {
			if (dis[r][v] == -1) {
				dis[r][v] = dis[r][u] + 1, qu.push(v);
			}
		}
	}
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
	// cout << "#encode\n";
	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 = 0; i < nh; ++i) bfs(i);
	for (int i = 1; i < nv; ++i) {
		for (int j = 0; j < 10; ++j) {
			encode_bit(par[i] >> j & 1);
		}
		// cout << par[i] << ' ';
	}
	// cout << '\n';
	for (int i = 0; i < nh; ++i) {
		for (int j = 0; j < 10; ++j) {
			encode_bit(dis[i][0] >> j & 1);
		}
		// cout << dis[i][0] << ' ';
	}
	// cout << '\n';
	vector< pair<int, int> > vec;
	for (int i = 0; i < nh; ++i) for (int j = 1; j < nv; ++j) vec.push_back({i, j});
	for (int i = 0; i < vec.size(); i += 5) {
		int val = 0, pw = 1;
		for (int j = i; j < min((int)vec.size(), i + 5); ++j) {
			int r = vec[j].first, u = vec[j].second;
			int tmp = dis[r][u] - dis[r][par[u]] + 1;
			// assert(0 <= tmp && tmp <= 2);
			val += tmp * pw, pw *= 3;
			// cout << tmp << ' ';
		}
		for (int j = 0; j < 8; ++j) encode_bit(val >> j & 1);
		// cout << '\n' << val << '\n';
	}
	// for (int i = 0; i < nh; ++i) {
	// 	for (int j = 0; j < nv; ++j) {
	// 		cout << dis[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
}

decoder

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

#include <bits/stdc++.h>

using namespace std;

static const int M = 36;
static const int N = 1000;

static int nh;
static int gap[M][N];
static int dis[M][N];
static vector<int> G[N];

static void dfs(int u) {
	for (auto v : G[u]) {
		for (int i = 0; i < nh; ++i) {
			dis[i][v] = dis[i][u] + gap[i][v];
		}
		dfs(v);
	}
}

void decode(int nv, int _nh) {
	nh = _nh;
	// cout << "#decode\n";
	for (int i = 1; i < nv; ++i) {
		int tmp = 0;
		for (int j = 0; j < 10; ++j) tmp += decode_bit() << j;
		G[tmp].push_back(i);
		// cout << tmp << ' ';
	}
	// cout << '\n';
	for (int i = 0; i < nh; ++i) {
		for (int j = 0; j < 10; ++j) {
			dis[i][0] += decode_bit() << j;
		}
		// cout << dis[i][0] << ' ';
	}
	// cout << '\n';
	vector< pair<int, int> > vec;
	for (int i = 0; i < nh; ++i) for (int j = 1; j < nv; ++j) vec.push_back({i, j});
	for (int i = 0; i < vec.size(); i += 5) {
		int val = 0;
		for (int j = 0; j < 8; ++j) {
			val += decode_bit() << j;
		}
		// cout << val << '\n';
		for (int j = i; j < min((int)vec.size(), i + 5); ++j) {
			// cout << val % 3 << ' ';
			gap[vec[j].first][vec[j].second] = val % 3 - 1, val /= 3;
		}
		// cout << '\n';
	}
	dfs(0);
	// for (int i = 0; i < nh; ++i) {
	// 	for (int j = 0; j < nv; ++j) {
	// 		cout << dis[i][j] << ' ';
	// 	}
	// 	cout << '\n';
	// }
	for (int i = 0; i < nh; ++i) {
		for (int j = 0; j < nv; ++j) {
			hops(i, j, dis[i][j]);
		}
	}
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i += 5) {
                  ~~^~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i += 5) {
                  ~~^~~~~~~~~~~~

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