oj.uz

Submission #676651

# Submission time Handle Problem Language Result Execution time Memory
676651 2022-12-31T15:25:59 Z nvujica Saveit (IOI10_saveit) C++14
0 / 100
 377 ms 79384 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 rek(int x, int p){
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(x2 == p) continue;
		
		ll b3 = 0;
		
		for(int j = 0; j < 36; 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 = 0; j < 10; j++){
			if(p & (1 << j)) encode_bit(1);
			else encode_bit(0);
		}
		
		for(int j = 0; j < 58; j++){
			if(b3 & (1LL << j)) encode_bit(1);
			else encode_bit(0);
		}
		
		rek(x2, x);
	}
}

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 = 0; j < 10; j++){
			if(dist[0][i] & (1 << j)) encode_bit(1);
			else encode_bit(0);
		}
	}
	
	rek(0, -1);
}
#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 'int rek(int, int)':
encoder.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
encoder.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
   41 | }
      | ^
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int j = 0; j < v[x].size(); j++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 79384 KB too many calls to encode_bit(b) function
2 Incorrect 88 ms 74336 KB too many calls to encode_bit(b) function
3 Incorrect 107 ms 74588 KB too many calls to encode_bit(b) function
4 Incorrect 91 ms 74340 KB too many calls to encode_bit(b) function
5 Incorrect 120 ms 74940 KB too many calls to encode_bit(b) function
6 Incorrect 102 ms 74728 KB too many calls to encode_bit(b) function
7 Incorrect 148 ms 75080 KB too many calls to encode_bit(b) function
8 Incorrect 118 ms 74560 KB too many calls to encode_bit(b) function
9 Incorrect 111 ms 74568 KB too many calls to encode_bit(b) function
10 Incorrect 107 ms 74572 KB too many calls to encode_bit(b) function
11 Incorrect 106 ms 74736 KB too many calls to encode_bit(b) function
12 Incorrect 100 ms 74476 KB too many calls to encode_bit(b) function
13 Incorrect 128 ms 75228 KB too many calls to encode_bit(b) function
14 Incorrect 94 ms 74600 KB too many calls to encode_bit(b) function
15 Incorrect 95 ms 74604 KB too many calls to encode_bit(b) function
16 Incorrect 121 ms 75060 KB too many calls to encode_bit(b) function
17 Incorrect 128 ms 75044 KB too many calls to encode_bit(b) function
18 Incorrect 134 ms 75284 KB too many calls to encode_bit(b) function
19 Incorrect 106 ms 74916 KB too many calls to encode_bit(b) function
20 Incorrect 146 ms 75616 KB too many calls to encode_bit(b) function
21 Incorrect 141 ms 75700 KB too many calls to encode_bit(b) function
22 Incorrect 119 ms 75216 KB too many calls to encode_bit(b) function
23 Incorrect 152 ms 75884 KB too many calls to encode_bit(b) function

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 79384 KB too many calls to encode_bit(b) function
2 Incorrect 88 ms 74336 KB too many calls to encode_bit(b) function
3 Incorrect 107 ms 74588 KB too many calls to encode_bit(b) function
4 Incorrect 91 ms 74340 KB too many calls to encode_bit(b) function
5 Incorrect 120 ms 74940 KB too many calls to encode_bit(b) function
6 Incorrect 102 ms 74728 KB too many calls to encode_bit(b) function
7 Incorrect 148 ms 75080 KB too many calls to encode_bit(b) function
8 Incorrect 118 ms 74560 KB too many calls to encode_bit(b) function
9 Incorrect 111 ms 74568 KB too many calls to encode_bit(b) function
10 Incorrect 107 ms 74572 KB too many calls to encode_bit(b) function
11 Incorrect 106 ms 74736 KB too many calls to encode_bit(b) function
12 Incorrect 100 ms 74476 KB too many calls to encode_bit(b) function
13 Incorrect 128 ms 75228 KB too many calls to encode_bit(b) function
14 Incorrect 94 ms 74600 KB too many calls to encode_bit(b) function
15 Incorrect 95 ms 74604 KB too many calls to encode_bit(b) function
16 Incorrect 121 ms 75060 KB too many calls to encode_bit(b) function
17 Incorrect 128 ms 75044 KB too many calls to encode_bit(b) function
18 Incorrect 134 ms 75284 KB too many calls to encode_bit(b) function
19 Incorrect 106 ms 74916 KB too many calls to encode_bit(b) function
20 Incorrect 146 ms 75616 KB too many calls to encode_bit(b) function
21 Incorrect 141 ms 75700 KB too many calls to encode_bit(b) function
22 Incorrect 119 ms 75216 KB too many calls to encode_bit(b) function
23 Incorrect 152 ms 75884 KB too many calls to encode_bit(b) function

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 79384 KB too many calls to encode_bit(b) function
2 Incorrect 88 ms 74336 KB too many calls to encode_bit(b) function
3 Incorrect 107 ms 74588 KB too many calls to encode_bit(b) function
4 Incorrect 91 ms 74340 KB too many calls to encode_bit(b) function
5 Incorrect 120 ms 74940 KB too many calls to encode_bit(b) function
6 Incorrect 102 ms 74728 KB too many calls to encode_bit(b) function
7 Incorrect 148 ms 75080 KB too many calls to encode_bit(b) function
8 Incorrect 118 ms 74560 KB too many calls to encode_bit(b) function
9 Incorrect 111 ms 74568 KB too many calls to encode_bit(b) function
10 Incorrect 107 ms 74572 KB too many calls to encode_bit(b) function
11 Incorrect 106 ms 74736 KB too many calls to encode_bit(b) function
12 Incorrect 100 ms 74476 KB too many calls to encode_bit(b) function
13 Incorrect 128 ms 75228 KB too many calls to encode_bit(b) function
14 Incorrect 94 ms 74600 KB too many calls to encode_bit(b) function
15 Incorrect 95 ms 74604 KB too many calls to encode_bit(b) function
16 Incorrect 121 ms 75060 KB too many calls to encode_bit(b) function
17 Incorrect 128 ms 75044 KB too many calls to encode_bit(b) function
18 Incorrect 134 ms 75284 KB too many calls to encode_bit(b) function
19 Incorrect 106 ms 74916 KB too many calls to encode_bit(b) function
20 Incorrect 146 ms 75616 KB too many calls to encode_bit(b) function
21 Incorrect 141 ms 75700 KB too many calls to encode_bit(b) function
22 Incorrect 119 ms 75216 KB too many calls to encode_bit(b) function
23 Incorrect 152 ms 75884 KB too many calls to encode_bit(b) function

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 79384 KB too many calls to encode_bit(b) function
2 Incorrect 88 ms 74336 KB too many calls to encode_bit(b) function
3 Incorrect 107 ms 74588 KB too many calls to encode_bit(b) function
4 Incorrect 91 ms 74340 KB too many calls to encode_bit(b) function
5 Incorrect 120 ms 74940 KB too many calls to encode_bit(b) function
6 Incorrect 102 ms 74728 KB too many calls to encode_bit(b) function
7 Incorrect 148 ms 75080 KB too many calls to encode_bit(b) function
8 Incorrect 118 ms 74560 KB too many calls to encode_bit(b) function
9 Incorrect 111 ms 74568 KB too many calls to encode_bit(b) function
10 Incorrect 107 ms 74572 KB too many calls to encode_bit(b) function
11 Incorrect 106 ms 74736 KB too many calls to encode_bit(b) function
12 Incorrect 100 ms 74476 KB too many calls to encode_bit(b) function
13 Incorrect 128 ms 75228 KB too many calls to encode_bit(b) function
14 Incorrect 94 ms 74600 KB too many calls to encode_bit(b) function
15 Incorrect 95 ms 74604 KB too many calls to encode_bit(b) function
16 Incorrect 121 ms 75060 KB too many calls to encode_bit(b) function
17 Incorrect 128 ms 75044 KB too many calls to encode_bit(b) function
18 Incorrect 134 ms 75284 KB too many calls to encode_bit(b) function
19 Incorrect 106 ms 74916 KB too many calls to encode_bit(b) function
20 Incorrect 146 ms 75616 KB too many calls to encode_bit(b) function
21 Incorrect 141 ms 75700 KB too many calls to encode_bit(b) function
22 Incorrect 119 ms 75216 KB too many calls to encode_bit(b) function
23 Incorrect 152 ms 75884 KB too many calls to encode_bit(b) function