oj.uz

Submission #212188

# Submission time Handle Problem Language Result Execution time Memory
212188 2020-03-22T12:46:09 Z mode149256 Saveit (IOI10_saveit) C++14
100 / 100
 269 ms 12016 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}


void dfs1(int x, int p, vii &ats, vii &fast, vii &edges, int N, int H, vi &par) {
	par[x] = p;
	// printf("einu x = %d, p = %d\n", x, p);
	for (int h = 0; h < H; ++h)
	{
		if (fast[h][x] == fast[h][p]) ats[h][x] = 0;
		else if (fast[h][x] + 1 == fast[h][p]) ats[h][x] = 1;
		else ats[h][x] = 2;
		// if (x == 1 and i == 0) printf("fx = %d, fp = %d, ats = %d\n", fast[x][i], fast[p][i], ats[x][i]);
	}

	for (auto u : edges[x])
		if (u != p)
			dfs1(u, x, ats, fast, edges, N, H, par);
}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
	vii edges;
	int N, H;
	N = nv;
	H = nh;
	int P = ne;
	edges = vii(N);
	vii visos(N);

	for (int i = 0; i < P; ++i)
	{
		int a = v1[i];
		int b = v2[i];
		visos[a].emplace_back(b);
		visos[b].emplace_back(a);
	}

	vii fast(H, vi(N, MOD));

	for (int i = 0; i < H; ++i)
	{
		fast[i][i] = 0;
		queue<int> q;
		q.push(i);
		while (q.size()) {
			int c = q.front(); q.pop();
			for (auto u : visos[c]) {
				if (fast[i][c] + 1 < fast[i][u]) {
					fast[i][u] = fast[i][c] + 1;
					q.push(u);
					if (!i) {
						edges[c].emplace_back(u);
						edges[u].emplace_back(c);
					}
				}
			}
		}
	}

	auto encode = [&](int a) {
		for (int i = 0; i < 10; ++i)
			encode_bit((a >> i) & 1);
	};

	// 0 - same
	// 1 - +1
	// 2 - -1
	vii ats(H, vi(N, 0));

	vi par(N);
	dfs1(0, 0, ats, fast, edges, N, H, par);

	for (int i = 1; i < N; ++i)
		encode(par[i]);
	// for (auto u : edges[0])
	// dfs1(u, 0, ats, fast, edges, N, H);

	auto encode_sm = [&](int a) {
		for (int i = 0; i < 2; ++i)
			encode_bit((a >> i) & 1);
	};

	// 3 skaiciai - 5 bitai
	map<vi, int> mapp;

	int piv = 0;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			for (int k = 0; k < 3; ++k)
			{
				mapp[vi({i, j, k})] = piv++;
			}
		}
	}

	auto encode5 = [&](int a) {
		for (int i = 0; i < 5; ++i)
			encode_bit((a >> i) & 1);
	};

	// printf("ats in encode\n");
	for (int i = 1; i < H; ++i)
	{
		int j = 1;
		for (; j + 2 < N; j += 3)
		{
			encode5(mapp[vi({ats[i][j], ats[i][j + 1], ats[i][j + 2]})]);

			// printf("%d ", ats[i][j]);
		}
		
		while (j < N) {
			encode_sm(ats[i][j]);
			j++;
		}

		// printf("\n");
	}
}

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

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}



void dfs2(int x, int p, vii &gautas, vii &ats, vii &edges, int N, int H) {

	for (int h = 0; h < H; ++h)
	{
		if (gautas[h][x] == 0) ats[h][x] = ats[h][p];
		else if (gautas[h][x] == 1) ats[h][x] = ats[h][p] - 1;
		else ats[h][x] = ats[h][p] + 1;
	}

	for (auto u : edges[x])
		if (u != p)
			dfs2(u, x, gautas, ats, edges, N, H);
}

void decode(int nv, int nh) {
	vii edges;
	int N, H;
	N = nv;
	H = nh;

	edges = vii(N);
	auto decode = [&]() -> int {
		int ret = 0;
		for (int i = 0; i < 10; ++i)
		{
			ret |= (decode_bit() << i);
		}
		// printf("decodinu %d\n", ret);
		return ret;
	};

	auto decode5 = [&]() {
		int ret = 0;
		for (int i = 0; i < 5; ++i)
			ret |= (decode_bit() << i);
		return ret;
	};

	auto decode_sm = [&]() -> int {
		int ret = 0;
		for (int i = 0; i < 2; ++i)
			ret |= (decode_bit() << i);
		return ret;
	};

	for (int i = 1; i < N; ++i)
	{
		int a = decode();
		edges[a].emplace_back(i);
		edges[i].emplace_back(a);
	}

	vii ats(H, vi(N, 0));

	ats[0] = vi(N, MOD);
	ats[0][0] = 0;
	queue<int> q;
	q.push(0);
	while (q.size()) {
		int c = q.front(); q.pop();
		for (auto u : edges[c]) {
			if (ats[0][c] + 1 < ats[0][u]) {
				ats[0][u] = ats[0][c] + 1;
				if (u < H) ats[u][0] = ats[0][u];
				q.push(u);
			}
		}
	}

	// print(ats[0]);
	vii gautas(H, vi(N, 2));
	for (int i = 0; i < H; ++i)
		gautas[i][0] = 0;

	// for (int i = 1; i < H; ++i)
	// {
	// 	for (int j = 1; j < N; ++j)
	// 	{
	// 		gautas[i][j] = decode_sm();
	// 	}
	// }

	// for (auto u : edges[0])
	// dfs2(u, 0, gautas, ats, edges, N, H);

	// printf("ats in decode\n");

	map<int, vi> mapp;
	int piv = 0;

	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < 3; ++j)
		{
			for (int k = 0; k < 3; ++k)
			{
				mapp[piv++] = vi({i, j, k});
			}
		}
	}

	for (int i = 1; i < H; ++i)
	{
		int j = 1;
		for (; j + 2 < N; j += 3)
		{
			vi c = mapp[decode5()];

			gautas[i][j] = c[0];
			gautas[i][j + 1] = c[1];
			gautas[i][j + 2] = c[2];

			// encode5(mapp[vi({ats[i][j], ats[i][j + 1], ats[i][j + 2]})]);

			// printf("%d ", ats[i][j]);
		}

		while (j < N) {
			gautas[i][j] = decode_sm();
			j++;
		}

		// printf("\n");
	}

	dfs2(0, 0, gautas, ats, edges, N, H);


	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			// printf("%d ", ats[i][j]);
			hops(i, j, ats[i][j]);
		}
		// printf("\n");
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12016 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 39 ms 6016 KB Output is correct - 61455 call(s) of encode_bit()
4 Correct 10 ms 4736 KB Output is correct - 68 call(s) of encode_bit()
5 Correct 36 ms 6212 KB Output is correct - 61455 call(s) of encode_bit()
6 Correct 43 ms 6300 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 55 ms 6624 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 35 ms 6024 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 37 ms 6384 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 39 ms 6144 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 49 ms 6292 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 39 ms 6192 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 68 ms 6648 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 36 ms 6324 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 44 ms 6272 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 62 ms 6784 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 66 ms 6656 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 65 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 48 ms 6580 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 85 ms 7036 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 93 ms 7300 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 74 ms 6812 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 92 ms 7676 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12016 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 39 ms 6016 KB Output is correct - 61455 call(s) of encode_bit()
4 Correct 10 ms 4736 KB Output is correct - 68 call(s) of encode_bit()
5 Correct 36 ms 6212 KB Output is correct - 61455 call(s) of encode_bit()
6 Correct 43 ms 6300 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 55 ms 6624 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 35 ms 6024 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 37 ms 6384 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 39 ms 6144 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 49 ms 6292 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 39 ms 6192 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 68 ms 6648 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 36 ms 6324 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 44 ms 6272 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 62 ms 6784 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 66 ms 6656 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 65 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 48 ms 6580 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 85 ms 7036 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 93 ms 7300 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 74 ms 6812 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 92 ms 7676 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12016 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 39 ms 6016 KB Output is correct - 61455 call(s) of encode_bit()
4 Correct 10 ms 4736 KB Output is correct - 68 call(s) of encode_bit()
5 Correct 36 ms 6212 KB Output is correct - 61455 call(s) of encode_bit()
6 Correct 43 ms 6300 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 55 ms 6624 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 35 ms 6024 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 37 ms 6384 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 39 ms 6144 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 49 ms 6292 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 39 ms 6192 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 68 ms 6648 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 36 ms 6324 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 44 ms 6272 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 62 ms 6784 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 66 ms 6656 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 65 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 48 ms 6580 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 85 ms 7036 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 93 ms 7300 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 74 ms 6812 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 92 ms 7676 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12016 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 54 call(s) of encode_bit()
3 Correct 39 ms 6016 KB Output is correct - 61455 call(s) of encode_bit()
4 Correct 10 ms 4736 KB Output is correct - 68 call(s) of encode_bit()
5 Correct 36 ms 6212 KB Output is correct - 61455 call(s) of encode_bit()
6 Correct 43 ms 6300 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 55 ms 6624 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 35 ms 6024 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 37 ms 6384 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 39 ms 6144 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 49 ms 6292 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 39 ms 6192 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 68 ms 6648 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 36 ms 6324 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 44 ms 6272 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 62 ms 6784 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 66 ms 6656 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 65 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 48 ms 6580 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 85 ms 7036 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 93 ms 7300 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 74 ms 6812 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 92 ms 7676 KB Output is correct - 68265 call(s) of encode_bit()