oj.uz

Submission #211992

# Submission time Handle Problem Language Result Execution time Memory
211992 2020-03-21T22:18:34 Z mode149256 Saveit (IOI10_saveit) C++14
0 / 100
 270 ms 12272 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 dfs(int x, int p, vii &ats, vii &fast, vii &edges, int N, int H) {
	// printf("einu x = %d, p = %d\n", x, p);
	if (x < H) {
		for (int i = 0; i < N; ++i)
		{
			if (fast[x][i] == fast[p][i]) ats[x][i] = 0;
			else if (fast[x][i] + 1 == fast[p][i]) ats[x][i] = 1;
			else ats[x][i] = 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)
			dfs(u, x, ats, fast, edges, N, H);
}

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);
	vpi trans;

	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) {
						trans.emplace_back(c, u);
						edges[c].emplace_back(u);
						edges[u].emplace_back(c);
					}
				}
			}
		}
	}

	// for (auto u : trans)
	// printf("%d %d\n", u.x, u.y);
	// assert((int)trans.size() == N - 1);

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

	for (auto u : trans) {
		encode(u.x);
		encode(u.y);
	}

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

	for (auto u : edges[0]) {
		dfs(u, 0, ats, fast, edges, N, H);
	}

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

	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			encode_sm(ats[i][j]);
		}
	}
	return;
}

#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';
}

vii edges;
int N, H;

void dfs(int x, int p, vii &gautas, vii &ats) {
	if (x < H) {
		for (int i = 0; i < N; ++i)
		{
			if (gautas[x][i] == 0) ats[x][i] = ats[p][i];
			else if (gautas[x][i] == 1) ats[x][i] = ats[p][i] - 1;
			else ats[x][i] = ats[p][i] + 1;
		}
	}

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

void decode(int nv, int nh) {
	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 decode_sm = [&]() -> int {
		int ret = 0;
		for (int i = 0; i < 2; ++i)
			ret |= (decode_bit() << i);
		return ret;
	};

	for (int i = 0; i < N - 1; ++i)
	{
		int a = decode();
		int b = decode();
		edges[a].emplace_back(b);
		edges[b].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;
				q.push(u);
			}
		}
	}

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

	for (auto u : edges[0]) {
		dfs(u, 0, gautas, ats);
	}

	for (int i = 0; i < H; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			hops(i, j, ats[i][j]);
		}
	}
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4820 KB Output is correct - 110 call(s) of encode_bit()
3 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 10 ms 4432 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 36 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 46 ms 3168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 17 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 20 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 40 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 49 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 30 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 58 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 69 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 41 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 74 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4820 KB Output is correct - 110 call(s) of encode_bit()
3 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 10 ms 4432 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 36 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 46 ms 3168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 17 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 20 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 40 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 49 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 30 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 58 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 69 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 41 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 74 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4820 KB Output is correct - 110 call(s) of encode_bit()
3 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 10 ms 4432 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 36 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 46 ms 3168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 17 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 20 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 40 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 49 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 30 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 58 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 69 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 41 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 74 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4820 KB Output is correct - 110 call(s) of encode_bit()
3 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 10 ms 4432 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 36 ms 2936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 15 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 15 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 19 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 46 ms 3168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 17 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 20 ms 2176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 40 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 49 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 30 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 58 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 69 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 41 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 74 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)