oj.uz

Submission #211991

# Submission time Handle Problem Language Result Execution time Memory
211991 2020-03-21T22:16:51 Z mode149256 Saveit (IOI10_saveit) C++14
0 / 100
 324 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 324 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4432 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 4560 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 17 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 38 ms 3296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 56 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 54 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 86 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 45 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 68 ms 4728 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 324 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4432 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 4560 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 17 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 38 ms 3296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 56 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 54 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 86 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 45 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 68 ms 4728 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 324 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4432 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 4560 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 17 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 38 ms 3296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 56 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 54 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 86 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 45 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 68 ms 4728 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 324 ms 12272 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4432 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 4560 KB Output is correct - 130 call(s) of encode_bit()
5 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 18 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 17 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 14 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 38 ms 3296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 18 ms 1920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 39 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 56 ms 3320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 54 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 86 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 45 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 68 ms 4728 KB Execution killed with signal 11 (could be triggered by violating memory limits)