oj.uz

답안 #534023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534023 2022-03-07T19:55:15 Z sidon 저장 (Saveit) (IOI10_saveit) C++17
100 / 100
 242 ms 10688 KB 
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"

const int Z = 1000;

int p[Z], d[Z];
bool vis[Z];
vector<int> g[Z];

void dfs(int u) {
	vis[u] = 1;
	for(const int &v : g[u]) if(!vis[v]) {
		dfs(v);
		p[v] = u;
	}
}

void encode(int n, int h, int m, int *a, int *b) {

	for(int i = 0; i < m; ++i) {
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}

	dfs(0);

	for(int i = 1; i < n; ++i)
		for(int j = 0; j < 10; ++j)
			encode_bit(bool(p[i] & (1<<j)));

	vector<int> x;

	for(int r = 0; r < h; ++r) {
		queue<int> q;
		fill(d, d + n, -1);
		q.push(r);
		d[r] = 0;

		while(!empty(q)) {
			int u = q.front(); q.pop();
			for(const int &v : g[u]) if(d[v] < 0)
				d[v] = d[u] + 1, q.push(v);
		}

		for(int u = 1; u < n; ++u)
			x.push_back(1 + d[u] - d[p[u]]);
	}

	while(size(x) % 3) x.push_back(0);

	for(int i = 0; i < int(size(x)); i += 3) {
		int num = x[i] + x[i + 1] * 3 + x[i + 2] * 9;
		for(int j = 0; j < 5; ++j)
			encode_bit(bool(num & (1<<j)));
	}
	return;
}
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "decoder.h"

const int Z = 1000;

int p[Z], w[Z], r;
vector<int> g[Z], x;

void dfs(int u, int par, int d) {
	hops(r, u, d);
	for(const int &v : g[u]) if(v != par)
		dfs(v, u, d + (u == p[v] ? w[v] : -w[u]));
}

void decode(int n, int h) {

	for(int i = 1; i < n; ++i) {
		for(int j = 0; j < 10; ++j)
			if(decode_bit()) p[i] |= 1<<j;
		g[i].push_back(p[i]);
		g[p[i]].push_back(i);
	}

	x.resize(n * h - h);
	while(size(x) % 3) x.push_back(0);

	for(int i = 0; i < int(size(x)); i += 3) {
		int num {};
		for(int j = 0; j < 5; ++j)
			if(decode_bit()) num |= 1<<j;

		for(int j = 0; j < 3; ++j, num /= 3)
			x[i + j] = (num % 3) - 1;
	}


	for(int pt = r = 0; r < h; ++r) {
		for(int u = 1; u < n; ++u)
			w[u] = x[pt++];
		dfs(r, r, 0);
	}
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 10688 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 5800 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 35 ms 5972 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 44 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 23 ms 5864 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 24 ms 5988 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 32 ms 5892 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 23 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 66 ms 6416 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 28 ms 6032 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 6088 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 61 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 45 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 54 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 37 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 83 ms 6932 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 86 ms 6956 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6480 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 7212 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 10688 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 5800 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 35 ms 5972 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 44 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 23 ms 5864 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 24 ms 5988 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 32 ms 5892 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 23 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 66 ms 6416 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 28 ms 6032 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 6088 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 61 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 45 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 54 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 37 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 83 ms 6932 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 86 ms 6956 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6480 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 7212 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 10688 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 5800 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 35 ms 5972 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 44 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 23 ms 5864 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 24 ms 5988 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 32 ms 5892 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 23 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 66 ms 6416 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 28 ms 6032 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 6088 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 61 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 45 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 54 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 37 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 83 ms 6932 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 86 ms 6956 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6480 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 7212 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 10688 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 24 ms 5800 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4588 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 35 ms 5972 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 44 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 23 ms 5864 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 26 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 24 ms 5988 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 32 ms 5892 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 23 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 66 ms 6416 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 28 ms 6032 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 6088 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 61 ms 6420 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 45 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 54 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 37 ms 6136 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 83 ms 6932 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 86 ms 6956 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 56 ms 6480 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 81 ms 7212 KB Output is correct - 69930 call(s) of encode_bit()