oj.uz

Submission #758749

# Submission time Handle Problem Language Result Execution time Memory
758749 2023-06-15T08:44:48 Z SanguineChameleon Saveit (IOI10_saveit) C++17
100 / 100
 147 ms 10624 KB 
#include "grader.h"
#include "encoder.h"

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

namespace encoder {
	const int maxn = 1e3 + 20;
	const int maxh = 40;
	vector<int> adj[maxn];
	int dist[maxh][maxn];
	bool flag[maxn];
	int par[maxn];
	long long diff[maxn];
	int n, h;

	void bfs(int s) {
		for (int i = 1; i <= n; i++) {
			dist[s][i] = -1;
		}
		dist[s][s] = 0;
		deque<int> q;
		q.push_back(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop_front();
			for (auto v: adj[u]) {
				if (dist[s][v] == -1) {
					dist[s][v] = dist[s][u] + 1;
					q.push_back(v);
				}
			}
		}
	}

	void dfs(int u) {
		flag[u] = true;
		for (auto v: adj[u]) {
			if (!flag[v]) {
				diff[v] = 0;
				for (int i = 1; i <= h; i++) {
					diff[v] = diff[v] * 3 + (dist[i][v] - dist[i][u] + 1);
				}
				par[v] = u;
				dfs(v);
			}
		}
	}
}

void encode(int n, int h, int m, int *x, int *y){
	encoder::n = n;
	encoder::h = h;
	for (int i = 0; i < m; i++) {
		int u = x[i] + 1;
		int v = y[i] + 1;
		encoder::adj[u].push_back(v);
		encoder::adj[v].push_back(u);
	}
	for (int i = 1; i <= h; i++) {
		encoder::bfs(i);
	}
	encoder::dfs(1);
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			encode_bit((encoder::par[i] >> j) & 1);
		}
		for (int j = 0; j < 58; j++) {
			encode_bit((encoder::diff[i] >> j) & 1);
		}
	}
}

#include "grader.h"
#include "decoder.h"

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

namespace decoder {
	const int maxn = 1e3 + 20;
	const int maxh = 40;
	long long diff[maxn];
	int dist[maxh][maxn];
	vector<int> ch[maxn];
	int n, h;

	void dfs(int u) {
		for (auto v: ch[u]) {
			for (int i = h; i >= 1; i--) {
				dist[i][v] = dist[i][u] + (diff[v] % 3 - 1);
				diff[v] /= 3;
			}
			dfs(v);
		}
	}
}

void decode(int n, int h) {
	decoder::n = n;
	decoder::h = h;
	for (int i = 2; i <= n; i++) {
		int par = 0;
		for (int j = 0; j < 10; j++) {
			par |= decode_bit() << j;
		}
		decoder::ch[par].push_back(i);
		for (int j = 0; j < 58; j++) {
			decoder::diff[i] |= (long long)decode_bit() << j;
		}
	}
	decoder::dfs(1);
	for (int i = 1; i <= h; i++) {
		int off = n;
		for (int j = 1; j <= n; j++) {
			off = min(off, decoder::dist[i][j]);
		}
		for (int j = 1; j <= n; j++) {
			hops(i - 1, j - 1, decoder::dist[i][j] - off);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10624 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 17 ms 5692 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 19 ms 5900 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 23 ms 6016 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 27 ms 6180 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 16 ms 5764 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 16 ms 5736 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 19 ms 5760 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 18 ms 5884 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 20 ms 5764 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 34 ms 6308 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 20 ms 5808 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 19 ms 5948 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 30 ms 6276 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 27 ms 6200 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 30 ms 6520 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 23 ms 6112 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 40 ms 6812 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 45 ms 7032 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 31 ms 6304 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 55 ms 7076 KB Output is correct - 67932 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10624 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 17 ms 5692 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 19 ms 5900 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 23 ms 6016 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 27 ms 6180 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 16 ms 5764 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 16 ms 5736 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 19 ms 5760 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 18 ms 5884 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 20 ms 5764 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 34 ms 6308 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 20 ms 5808 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 19 ms 5948 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 30 ms 6276 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 27 ms 6200 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 30 ms 6520 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 23 ms 6112 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 40 ms 6812 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 45 ms 7032 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 31 ms 6304 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 55 ms 7076 KB Output is correct - 67932 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10624 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 17 ms 5692 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 19 ms 5900 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 23 ms 6016 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 27 ms 6180 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 16 ms 5764 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 16 ms 5736 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 19 ms 5760 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 18 ms 5884 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 20 ms 5764 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 34 ms 6308 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 20 ms 5808 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 19 ms 5948 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 30 ms 6276 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 27 ms 6200 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 30 ms 6520 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 23 ms 6112 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 40 ms 6812 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 45 ms 7032 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 31 ms 6304 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 55 ms 7076 KB Output is correct - 67932 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10624 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 3 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 17 ms 5692 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 19 ms 5900 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 23 ms 6016 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 27 ms 6180 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 16 ms 5764 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 16 ms 5736 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 19 ms 5760 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 18 ms 5884 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 20 ms 5764 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 34 ms 6308 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 20 ms 5808 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 19 ms 5948 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 30 ms 6276 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 27 ms 6200 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 30 ms 6520 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 23 ms 6112 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 40 ms 6812 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 45 ms 7032 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 31 ms 6304 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 55 ms 7076 KB Output is correct - 67932 call(s) of encode_bit()