oj.uz

Submission #463547

# Submission time Handle Problem Language Result Execution time Memory
463547 2021-08-11T10:03:25 Z nonsensenonsense1 Saveit (IOI10_saveit) C++17
100 / 100
 347 ms 10308 KB 
#include "grader.h"
#include <cstring>
#include <vector>
#include <queue>

const int N = 1000;
int pr[N], dist[N];
static std::vector<int> g[N];

static void dfs(int v) 
{
	for (int i = 0; i < (int)g[v].size(); ++i) if (!pr[g[v][i]]) {
		pr[g[v][i]] = v + 1;
		dfs(g[v][i]);
	}
}

void encode(int n, int h, int p, int *a, int *b) 
{
	for (int i = 0; i < p; ++i) {
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	dfs(0);
	for (int i = 1; i < n; ++i) {
		--pr[i];
		for (int j = 0; j < 10; ++j) encode_bit(pr[i] >> j & 1);
	}
	for (int i = 0; i < h; ++i) {
		memset(dist, -1, n << 2);
		std::queue<int> q;
		dist[i] = 0;
		q.push(i);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (int i = 0; i < (int)g[v].size(); ++i) if (dist[g[v][i]] == -1) {
				dist[g[v][i]] = dist[v] + 1;
				q.push(g[v][i]);
			}
		}
		for (int i = 1; i < n; i += 3) {
			int x = 0;
			for (int j = 0; j < 3; ++j) {
				x *= 3;
				if (i + j < n) {
					if (dist[i + j] == dist[pr[i + j]]) ++x;
					else if (dist[i + j] > dist[pr[i + j]]) x += 2;
				}
			}
			for (int j = 0; j < 5; ++j) encode_bit(x >> j & 1);
		}
	}
}

#include "grader.h"
#include <cstring>
#include <vector>

const int N = 1000;
int p[N], cur, len[N], up[N];
static std::vector<int> g[N];

static void dfs(int v) 
{
	hops(cur, v, len[v] - 1);
	if (v && !len[p[v]]) {
		len[p[v]] = len[v];
		if (!up[v]) ++len[p[v]];
		else if (up[v] == 2) --len[p[v]];
		dfs(p[v]);
	}
	for (int i = 0; i < (int)g[v].size(); ++i) if (!len[g[v][i]]) {
		len[g[v][i]] = len[v];
		if (!up[g[v][i]]) --len[g[v][i]];
		else if (up[g[v][i]] == 2) ++len[g[v][i]];
		dfs(g[v][i]);
	}
}

void decode(int n, int h) 
{
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 10; ++j) p[i] |= decode_bit() << j;
		g[p[i]].push_back(i);
	}
	for (int i = 0; i < h; ++i) {
		for (int j = 1; j < n; j += 3) {
			int x = 0;
			for (int k = 0; k < 5; ++k) x |= decode_bit() << k;
			for (int k = 2; k >= 0; --k) {
				if (j + k < n) up[j + k] = x % 3;
				x /= 3;
			}
			x /= 3;
		}
		cur = i;
		memset(len, 0, n << 2);
		len[i] = 1;
		dfs(i);
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 10308 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5356 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 30 ms 5424 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 30 ms 5540 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 43 ms 6040 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 26 ms 5460 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 27 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 32 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 31 ms 5532 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 33 ms 5324 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 77 ms 6036 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5488 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 32 ms 5460 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 56 ms 5932 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 48 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 42 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 102 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 54 ms 6152 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 104 ms 6708 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 10308 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5356 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 30 ms 5424 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 30 ms 5540 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 43 ms 6040 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 26 ms 5460 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 27 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 32 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 31 ms 5532 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 33 ms 5324 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 77 ms 6036 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5488 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 32 ms 5460 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 56 ms 5932 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 48 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 42 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 102 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 54 ms 6152 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 104 ms 6708 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 10308 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5356 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 30 ms 5424 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 30 ms 5540 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 43 ms 6040 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 26 ms 5460 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 27 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 32 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 31 ms 5532 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 33 ms 5324 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 77 ms 6036 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5488 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 32 ms 5460 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 56 ms 5932 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 48 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 42 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 102 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 54 ms 6152 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 104 ms 6708 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 10308 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4580 KB Output is correct - 70 call(s) of encode_bit()
3 Correct 26 ms 5356 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4588 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 30 ms 5424 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 30 ms 5540 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 43 ms 6040 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 26 ms 5460 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 27 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 32 ms 5456 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 31 ms 5532 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 33 ms 5324 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 77 ms 6036 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 31 ms 5488 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 32 ms 5460 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 68 ms 5928 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 56 ms 5932 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 48 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 42 ms 5732 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 72 ms 6376 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 102 ms 6592 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 54 ms 6152 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 104 ms 6708 KB Output is correct - 69930 call(s) of encode_bit()