oj.uz

Submission #62654

# Submission time Handle Problem Language Result Execution time Memory
62654 2018-07-29T16:17:22 Z aome Saveit (IOI10_saveit) C++17
100 / 100
 438 ms 12520 KB 
#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';
	// }
}

#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 12520 KB Output is correct - 67894 call(s) of encode_bit()
2 Correct 7 ms 4848 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 6472 KB Output is correct - 61134 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 122 call(s) of encode_bit()
5 Correct 32 ms 6984 KB Output is correct - 61134 call(s) of encode_bit()
6 Correct 34 ms 6964 KB Output is correct - 67894 call(s) of encode_bit()
7 Correct 88 ms 7416 KB Output is correct - 67894 call(s) of encode_bit()
8 Correct 30 ms 6716 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 6720 KB Output is correct - 67894 call(s) of encode_bit()
10 Correct 31 ms 6684 KB Output is correct - 67894 call(s) of encode_bit()
11 Correct 43 ms 6836 KB Output is correct - 67894 call(s) of encode_bit()
12 Correct 32 ms 6676 KB Output is correct - 67894 call(s) of encode_bit()
13 Correct 67 ms 7352 KB Output is correct - 67894 call(s) of encode_bit()
14 Correct 32 ms 6832 KB Output is correct - 67894 call(s) of encode_bit()
15 Correct 33 ms 6908 KB Output is correct - 67894 call(s) of encode_bit()
16 Correct 50 ms 7232 KB Output is correct - 67894 call(s) of encode_bit()
17 Correct 61 ms 7168 KB Output is correct - 67894 call(s) of encode_bit()
18 Correct 87 ms 7564 KB Output is correct - 67894 call(s) of encode_bit()
19 Correct 77 ms 7164 KB Output is correct - 67894 call(s) of encode_bit()
20 Correct 91 ms 7772 KB Output is correct - 67894 call(s) of encode_bit()
21 Correct 102 ms 7916 KB Output is correct - 67894 call(s) of encode_bit()
22 Correct 64 ms 7492 KB Output is correct - 67894 call(s) of encode_bit()
23 Correct 82 ms 8284 KB Output is correct - 67894 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 12520 KB Output is correct - 67894 call(s) of encode_bit()
2 Correct 7 ms 4848 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 6472 KB Output is correct - 61134 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 122 call(s) of encode_bit()
5 Correct 32 ms 6984 KB Output is correct - 61134 call(s) of encode_bit()
6 Correct 34 ms 6964 KB Output is correct - 67894 call(s) of encode_bit()
7 Correct 88 ms 7416 KB Output is correct - 67894 call(s) of encode_bit()
8 Correct 30 ms 6716 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 6720 KB Output is correct - 67894 call(s) of encode_bit()
10 Correct 31 ms 6684 KB Output is correct - 67894 call(s) of encode_bit()
11 Correct 43 ms 6836 KB Output is correct - 67894 call(s) of encode_bit()
12 Correct 32 ms 6676 KB Output is correct - 67894 call(s) of encode_bit()
13 Correct 67 ms 7352 KB Output is correct - 67894 call(s) of encode_bit()
14 Correct 32 ms 6832 KB Output is correct - 67894 call(s) of encode_bit()
15 Correct 33 ms 6908 KB Output is correct - 67894 call(s) of encode_bit()
16 Correct 50 ms 7232 KB Output is correct - 67894 call(s) of encode_bit()
17 Correct 61 ms 7168 KB Output is correct - 67894 call(s) of encode_bit()
18 Correct 87 ms 7564 KB Output is correct - 67894 call(s) of encode_bit()
19 Correct 77 ms 7164 KB Output is correct - 67894 call(s) of encode_bit()
20 Correct 91 ms 7772 KB Output is correct - 67894 call(s) of encode_bit()
21 Correct 102 ms 7916 KB Output is correct - 67894 call(s) of encode_bit()
22 Correct 64 ms 7492 KB Output is correct - 67894 call(s) of encode_bit()
23 Correct 82 ms 8284 KB Output is correct - 67894 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 12520 KB Output is correct - 67894 call(s) of encode_bit()
2 Correct 7 ms 4848 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 6472 KB Output is correct - 61134 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 122 call(s) of encode_bit()
5 Correct 32 ms 6984 KB Output is correct - 61134 call(s) of encode_bit()
6 Correct 34 ms 6964 KB Output is correct - 67894 call(s) of encode_bit()
7 Correct 88 ms 7416 KB Output is correct - 67894 call(s) of encode_bit()
8 Correct 30 ms 6716 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 6720 KB Output is correct - 67894 call(s) of encode_bit()
10 Correct 31 ms 6684 KB Output is correct - 67894 call(s) of encode_bit()
11 Correct 43 ms 6836 KB Output is correct - 67894 call(s) of encode_bit()
12 Correct 32 ms 6676 KB Output is correct - 67894 call(s) of encode_bit()
13 Correct 67 ms 7352 KB Output is correct - 67894 call(s) of encode_bit()
14 Correct 32 ms 6832 KB Output is correct - 67894 call(s) of encode_bit()
15 Correct 33 ms 6908 KB Output is correct - 67894 call(s) of encode_bit()
16 Correct 50 ms 7232 KB Output is correct - 67894 call(s) of encode_bit()
17 Correct 61 ms 7168 KB Output is correct - 67894 call(s) of encode_bit()
18 Correct 87 ms 7564 KB Output is correct - 67894 call(s) of encode_bit()
19 Correct 77 ms 7164 KB Output is correct - 67894 call(s) of encode_bit()
20 Correct 91 ms 7772 KB Output is correct - 67894 call(s) of encode_bit()
21 Correct 102 ms 7916 KB Output is correct - 67894 call(s) of encode_bit()
22 Correct 64 ms 7492 KB Output is correct - 67894 call(s) of encode_bit()
23 Correct 82 ms 8284 KB Output is correct - 67894 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 12520 KB Output is correct - 67894 call(s) of encode_bit()
2 Correct 7 ms 4848 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 31 ms 6472 KB Output is correct - 61134 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 122 call(s) of encode_bit()
5 Correct 32 ms 6984 KB Output is correct - 61134 call(s) of encode_bit()
6 Correct 34 ms 6964 KB Output is correct - 67894 call(s) of encode_bit()
7 Correct 88 ms 7416 KB Output is correct - 67894 call(s) of encode_bit()
8 Correct 30 ms 6716 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 6720 KB Output is correct - 67894 call(s) of encode_bit()
10 Correct 31 ms 6684 KB Output is correct - 67894 call(s) of encode_bit()
11 Correct 43 ms 6836 KB Output is correct - 67894 call(s) of encode_bit()
12 Correct 32 ms 6676 KB Output is correct - 67894 call(s) of encode_bit()
13 Correct 67 ms 7352 KB Output is correct - 67894 call(s) of encode_bit()
14 Correct 32 ms 6832 KB Output is correct - 67894 call(s) of encode_bit()
15 Correct 33 ms 6908 KB Output is correct - 67894 call(s) of encode_bit()
16 Correct 50 ms 7232 KB Output is correct - 67894 call(s) of encode_bit()
17 Correct 61 ms 7168 KB Output is correct - 67894 call(s) of encode_bit()
18 Correct 87 ms 7564 KB Output is correct - 67894 call(s) of encode_bit()
19 Correct 77 ms 7164 KB Output is correct - 67894 call(s) of encode_bit()
20 Correct 91 ms 7772 KB Output is correct - 67894 call(s) of encode_bit()
21 Correct 102 ms 7916 KB Output is correct - 67894 call(s) of encode_bit()
22 Correct 64 ms 7492 KB Output is correct - 67894 call(s) of encode_bit()
23 Correct 82 ms 8284 KB Output is correct - 67894 call(s) of encode_bit()