oj.uz

Submission #211994

# Submission time Handle Problem Language Result Execution time Memory
211994 2020-03-21T22:19:44 Z mode149256 Saveit (IOI10_saveit) C++14
0 / 100
 370 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 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';
}



void dfs(int x, int p, vii &gautas, vii &ats, vii &edges, int N, int H) {
	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, 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 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, edges, N, H);
	}

	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 370 ms 12016 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4760 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 11 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 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2936 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 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2176 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 44 ms 3120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 17 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 41 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 46 ms 3324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 26 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 64 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 51 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 73 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 370 ms 12016 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4760 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 11 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 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2936 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 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2176 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 44 ms 3120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 17 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 41 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 46 ms 3324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 26 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 64 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 51 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 73 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 370 ms 12016 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4760 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 11 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 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2936 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 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2176 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 44 ms 3120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 17 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 41 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 46 ms 3324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 26 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 64 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 51 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 73 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 370 ms 12016 KB Output is partially correct - 91980 call(s) of encode_bit()
2 Correct 10 ms 4760 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 11 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 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 2936 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 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 18 ms 2176 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 44 ms 3120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 16 ms 1792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 17 ms 2048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 41 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 41 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 46 ms 3324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 26 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 62 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 64 ms 4088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 51 ms 3192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 73 ms 4600 KB Execution killed with signal 11 (could be triggered by violating memory limits)