oj.uz

Submission #743834

# Submission time Handle Problem Language Result Execution time Memory
743834 2023-05-18T04:21:52 Z boyliguanhan Saveit (IOI10_saveit) C++17
100 / 100
 282 ms 10796 KB 
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#include "grader.h"
#include "encoder.h"
#define N 1010
static int p[N], d[N];
bool vis[N];
static vector<int> adj[N];
void dfs(int n) {
	vis[n] = 1;
	for(auto i : adj[n])
    if(!vis[i])
	    dfs(i), p[i] = n;
}
void encode(int n, int h, int m, int *A, int *B) {
	for(int i = 0; i < m; ++i) {
		adj[A[i]].PB(B[i]);
		adj[B[i]].PB(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 i = 0; i < h; ++i) {
		queue<int> q;
		memset(d, -1, sizeof d);
		q.push(i);
		d[i] = 0;
		while(!empty(q)) {
			int u = q.front(); q.pop();
			for(auto v : adj[u]) if(d[v] < 0)
				d[v] = d[u] + 1, q.push(v);
		}
		for(int u = 1; u < n; ++u)
			x.PB(1 + d[u] - d[p[u]]);
	}
	while(size(x) % 3) x.PB(0);
	for(int i = 0; i < 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"
#define N 1000
#define PB push_back
static int p[N], dif[N], H;
static vector<int> adj[N], x;
void dfs(int n, int par, int d) {
	hops(H, n, d);
	for(auto v : adj[n]) if(v != par)
		dfs(v, n, d + (n == p[v] ? dif[v] : -dif[n]));
}
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;
		adj[i].PB(p[i]);
		adj[p[i]].PB(i);
	}
	x.resize(n * h - h);
	while(size(x) % 3) x.PB(0);
	for(int i = 0; i < size(x); i += 3) {
		int num=0;
		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 pos = H = 0; H < h; ++H) {
		for(int u = 1; u < n; ++u)
			dif[u] = x[pos++];
		dfs(H, H, 0);
	}
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i = 0; i < size(x); i += 3) {
      |                 ~~^~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i = 0; i < size(x); i += 3) {
      |                 ~~^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 10796 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 20 ms 5712 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 22 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 6056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 36 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5884 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 25 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 23 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 6012 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5964 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 41 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 24 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 40 ms 6432 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 43 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 43 ms 6544 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 32 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 60 ms 7076 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 66 ms 6940 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 40 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 72 ms 7232 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 10796 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 20 ms 5712 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 22 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 6056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 36 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5884 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 25 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 23 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 6012 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5964 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 41 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 24 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 40 ms 6432 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 43 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 43 ms 6544 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 32 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 60 ms 7076 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 66 ms 6940 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 40 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 72 ms 7232 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 10796 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 20 ms 5712 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 22 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 6056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 36 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5884 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 25 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 23 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 6012 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5964 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 41 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 24 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 40 ms 6432 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 43 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 43 ms 6544 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 32 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 60 ms 7076 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 66 ms 6940 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 40 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 72 ms 7232 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 10796 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 20 ms 5712 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 22 ms 5960 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 27 ms 6056 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 36 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 25 ms 5884 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 25 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 23 ms 5868 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 26 ms 6012 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 5964 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 41 ms 6444 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 24 ms 5996 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 24 ms 6008 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 40 ms 6432 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 43 ms 6368 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 43 ms 6544 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 32 ms 6144 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 60 ms 7076 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 66 ms 6940 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 40 ms 6536 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 72 ms 7232 KB Output is correct - 69930 call(s) of encode_bit()