oj.uz

Submission #676661

# Submission time Handle Problem Language Result Execution time Memory
676661 2022-12-31T15:54:33 Z nvujica Saveit (IOI10_saveit) C++14
0 / 100
 295 ms 10392 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
#define ll long long

using namespace std;

const int maxn = 1005, maxh = 40;

int dist[maxh][maxn];
queue <int> q;
vector <int> v[maxn];
int bio[maxn];

void rek(int x, int p, int h){
	bio[x] = 1;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(bio[x2]) continue;
		
		ll b3 = 0;
		
		for(int j = 0; j < h; j++){
			b3 *= 3;
			
			if(dist[j][x2] - dist[j][x] == 1) b3 += 1;
			else if(dist[j][x2] - dist[j][x] == -1) b3 += 2; 
		}
		
		for(int j = 9; j >= 0; j--){
			if(p & (1 << j)) encode_bit(1);
			else encode_bit(0);
		}
		
		for(int j = 57; j >= 0; j--){
			if(b3 & (1LL << j)) encode_bit(1);
			else encode_bit(0);
		}
		
		rek(x2, x, h);
	}
}

void encode(int n, int h, int p, int *a, int *b){
	memset(dist, -1, sizeof dist);
	
	for(int i = 0; i < p; i++){
		v[a[i]].push_back(b[i]);
		v[b[i]].push_back(a[i]);
	}
	
	for(int i = 0; i < h; i++){
		dist[i][i] = 0;
		q.push(i);
		
		while(!q.empty()){
			int x = q.front();
			q.pop();
			
			for(int j = 0; j < v[x].size(); j++){
				int x2 = v[x][j];
				
				if(dist[i][x2] == -1){
					dist[i][x2] = dist[i][x] + 1;
					q.push(x2);
				}
			}
		}
	}
	
	for(int i = 0; i < h; i++){
		for(int j = 9; j >= 0; j--){
			if(dist[0][i] & (1 << j)) encode_bit(1);
			else encode_bit(0);
		}
	}
	
	rek(0, -1, h);
}
#include <bits/stdc++.h>
#define ll long long
#include "grader.h"
#include "decoder.h"

using namespace std;

const int maxn = 1005, maxh = 40;

int dist[maxh][maxn];

void decode(int n, int h){
	for(int i = 0; i < h; i++){
		for(int j = 0; j < 10; j++){
			dist[0][i] *= 2;
			dist[0][i] += decode_bit();
		}
	}
	
	for(int i = 1; i < n; i++){
		int p = 0;
		
		for(int j = 0; j < 10; j++){
			p *= 2;
			p += decode_bit();
		}
		
		ll b3 = 0;
		
		for(int j = 0; j < 58; j++){
			b3 *= 2;
			b3 += decode_bit();
		}
		
		for(int j = 0; j < h; j++){
			int x = b3 % 3;
			
			if(x == 0) dist[j][i] = dist[j][p];
			if(x == 1) dist[j][i] = dist[j][p] + 1;
			if(x == 2) dist[j][i] = dist[j][p] - 1;
			
			b3 /= 3;
		}
	}
	
	for(int i = 0; i < h; i++){
		for(int j = 0; j < n; j++){
			hops(i, j, dist[i][j]);
		}
	}
}

Compilation message

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 10392 KB wrong parameter
2 Incorrect 3 ms 4680 KB wrong parameter
3 Incorrect 16 ms 5620 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 22 ms 5736 KB wrong parameter
6 Incorrect 20 ms 5844 KB wrong parameter
7 Incorrect 35 ms 6156 KB wrong parameter
8 Incorrect 20 ms 5620 KB wrong parameter
9 Incorrect 19 ms 5620 KB wrong parameter
10 Incorrect 17 ms 5636 KB wrong parameter
11 Incorrect 40 ms 5752 KB wrong parameter
12 Incorrect 16 ms 5664 KB wrong parameter
13 Incorrect 52 ms 6300 KB wrong parameter
14 Incorrect 17 ms 5640 KB wrong parameter
15 Incorrect 18 ms 5736 KB wrong parameter
16 Incorrect 51 ms 6152 KB wrong parameter
17 Incorrect 41 ms 6116 KB wrong parameter
18 Incorrect 54 ms 6316 KB wrong parameter
19 Incorrect 28 ms 6024 KB wrong parameter
20 Incorrect 53 ms 6596 KB wrong parameter
21 Incorrect 61 ms 6824 KB wrong parameter
22 Incorrect 40 ms 6304 KB wrong parameter
23 Incorrect 63 ms 6996 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 10392 KB wrong parameter
2 Incorrect 3 ms 4680 KB wrong parameter
3 Incorrect 16 ms 5620 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 22 ms 5736 KB wrong parameter
6 Incorrect 20 ms 5844 KB wrong parameter
7 Incorrect 35 ms 6156 KB wrong parameter
8 Incorrect 20 ms 5620 KB wrong parameter
9 Incorrect 19 ms 5620 KB wrong parameter
10 Incorrect 17 ms 5636 KB wrong parameter
11 Incorrect 40 ms 5752 KB wrong parameter
12 Incorrect 16 ms 5664 KB wrong parameter
13 Incorrect 52 ms 6300 KB wrong parameter
14 Incorrect 17 ms 5640 KB wrong parameter
15 Incorrect 18 ms 5736 KB wrong parameter
16 Incorrect 51 ms 6152 KB wrong parameter
17 Incorrect 41 ms 6116 KB wrong parameter
18 Incorrect 54 ms 6316 KB wrong parameter
19 Incorrect 28 ms 6024 KB wrong parameter
20 Incorrect 53 ms 6596 KB wrong parameter
21 Incorrect 61 ms 6824 KB wrong parameter
22 Incorrect 40 ms 6304 KB wrong parameter
23 Incorrect 63 ms 6996 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 10392 KB wrong parameter
2 Incorrect 3 ms 4680 KB wrong parameter
3 Incorrect 16 ms 5620 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 22 ms 5736 KB wrong parameter
6 Incorrect 20 ms 5844 KB wrong parameter
7 Incorrect 35 ms 6156 KB wrong parameter
8 Incorrect 20 ms 5620 KB wrong parameter
9 Incorrect 19 ms 5620 KB wrong parameter
10 Incorrect 17 ms 5636 KB wrong parameter
11 Incorrect 40 ms 5752 KB wrong parameter
12 Incorrect 16 ms 5664 KB wrong parameter
13 Incorrect 52 ms 6300 KB wrong parameter
14 Incorrect 17 ms 5640 KB wrong parameter
15 Incorrect 18 ms 5736 KB wrong parameter
16 Incorrect 51 ms 6152 KB wrong parameter
17 Incorrect 41 ms 6116 KB wrong parameter
18 Incorrect 54 ms 6316 KB wrong parameter
19 Incorrect 28 ms 6024 KB wrong parameter
20 Incorrect 53 ms 6596 KB wrong parameter
21 Incorrect 61 ms 6824 KB wrong parameter
22 Incorrect 40 ms 6304 KB wrong parameter
23 Incorrect 63 ms 6996 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 10392 KB wrong parameter
2 Incorrect 3 ms 4680 KB wrong parameter
3 Incorrect 16 ms 5620 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 22 ms 5736 KB wrong parameter
6 Incorrect 20 ms 5844 KB wrong parameter
7 Incorrect 35 ms 6156 KB wrong parameter
8 Incorrect 20 ms 5620 KB wrong parameter
9 Incorrect 19 ms 5620 KB wrong parameter
10 Incorrect 17 ms 5636 KB wrong parameter
11 Incorrect 40 ms 5752 KB wrong parameter
12 Incorrect 16 ms 5664 KB wrong parameter
13 Incorrect 52 ms 6300 KB wrong parameter
14 Incorrect 17 ms 5640 KB wrong parameter
15 Incorrect 18 ms 5736 KB wrong parameter
16 Incorrect 51 ms 6152 KB wrong parameter
17 Incorrect 41 ms 6116 KB wrong parameter
18 Incorrect 54 ms 6316 KB wrong parameter
19 Incorrect 28 ms 6024 KB wrong parameter
20 Incorrect 53 ms 6596 KB wrong parameter
21 Incorrect 61 ms 6824 KB wrong parameter
22 Incorrect 40 ms 6304 KB wrong parameter
23 Incorrect 63 ms 6996 KB wrong parameter