oj.uz

Submission #676652

# Submission time Handle Problem Language Result Execution time Memory
676652 2022-12-31T15:30:28 Z nvujica Saveit (IOI10_saveit) C++14
0 / 100
 212 ms 10456 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){
	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 < 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 'void rek(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 212 ms 10456 KB wrong parameter
2 Incorrect 3 ms 4720 KB wrong parameter
3 Incorrect 17 ms 5568 KB wrong parameter
4 Incorrect 3 ms 4744 KB wrong parameter
5 Incorrect 19 ms 5864 KB wrong parameter
6 Incorrect 26 ms 5900 KB wrong parameter
7 Incorrect 35 ms 6232 KB wrong parameter
8 Incorrect 20 ms 5564 KB wrong parameter
9 Incorrect 18 ms 5596 KB wrong parameter
10 Incorrect 21 ms 5572 KB wrong parameter
11 Incorrect 23 ms 5756 KB wrong parameter
12 Incorrect 17 ms 5620 KB wrong parameter
13 Incorrect 56 ms 6364 KB wrong parameter
14 Incorrect 20 ms 5620 KB wrong parameter
15 Incorrect 18 ms 5740 KB wrong parameter
16 Incorrect 37 ms 6244 KB wrong parameter
17 Incorrect 49 ms 6052 KB wrong parameter
18 Incorrect 51 ms 6360 KB wrong parameter
19 Incorrect 28 ms 5996 KB wrong parameter
20 Incorrect 64 ms 6660 KB wrong parameter
21 Incorrect 61 ms 6788 KB wrong parameter
22 Incorrect 49 ms 6240 KB wrong parameter
23 Incorrect 83 ms 6968 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10456 KB wrong parameter
2 Incorrect 3 ms 4720 KB wrong parameter
3 Incorrect 17 ms 5568 KB wrong parameter
4 Incorrect 3 ms 4744 KB wrong parameter
5 Incorrect 19 ms 5864 KB wrong parameter
6 Incorrect 26 ms 5900 KB wrong parameter
7 Incorrect 35 ms 6232 KB wrong parameter
8 Incorrect 20 ms 5564 KB wrong parameter
9 Incorrect 18 ms 5596 KB wrong parameter
10 Incorrect 21 ms 5572 KB wrong parameter
11 Incorrect 23 ms 5756 KB wrong parameter
12 Incorrect 17 ms 5620 KB wrong parameter
13 Incorrect 56 ms 6364 KB wrong parameter
14 Incorrect 20 ms 5620 KB wrong parameter
15 Incorrect 18 ms 5740 KB wrong parameter
16 Incorrect 37 ms 6244 KB wrong parameter
17 Incorrect 49 ms 6052 KB wrong parameter
18 Incorrect 51 ms 6360 KB wrong parameter
19 Incorrect 28 ms 5996 KB wrong parameter
20 Incorrect 64 ms 6660 KB wrong parameter
21 Incorrect 61 ms 6788 KB wrong parameter
22 Incorrect 49 ms 6240 KB wrong parameter
23 Incorrect 83 ms 6968 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10456 KB wrong parameter
2 Incorrect 3 ms 4720 KB wrong parameter
3 Incorrect 17 ms 5568 KB wrong parameter
4 Incorrect 3 ms 4744 KB wrong parameter
5 Incorrect 19 ms 5864 KB wrong parameter
6 Incorrect 26 ms 5900 KB wrong parameter
7 Incorrect 35 ms 6232 KB wrong parameter
8 Incorrect 20 ms 5564 KB wrong parameter
9 Incorrect 18 ms 5596 KB wrong parameter
10 Incorrect 21 ms 5572 KB wrong parameter
11 Incorrect 23 ms 5756 KB wrong parameter
12 Incorrect 17 ms 5620 KB wrong parameter
13 Incorrect 56 ms 6364 KB wrong parameter
14 Incorrect 20 ms 5620 KB wrong parameter
15 Incorrect 18 ms 5740 KB wrong parameter
16 Incorrect 37 ms 6244 KB wrong parameter
17 Incorrect 49 ms 6052 KB wrong parameter
18 Incorrect 51 ms 6360 KB wrong parameter
19 Incorrect 28 ms 5996 KB wrong parameter
20 Incorrect 64 ms 6660 KB wrong parameter
21 Incorrect 61 ms 6788 KB wrong parameter
22 Incorrect 49 ms 6240 KB wrong parameter
23 Incorrect 83 ms 6968 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10456 KB wrong parameter
2 Incorrect 3 ms 4720 KB wrong parameter
3 Incorrect 17 ms 5568 KB wrong parameter
4 Incorrect 3 ms 4744 KB wrong parameter
5 Incorrect 19 ms 5864 KB wrong parameter
6 Incorrect 26 ms 5900 KB wrong parameter
7 Incorrect 35 ms 6232 KB wrong parameter
8 Incorrect 20 ms 5564 KB wrong parameter
9 Incorrect 18 ms 5596 KB wrong parameter
10 Incorrect 21 ms 5572 KB wrong parameter
11 Incorrect 23 ms 5756 KB wrong parameter
12 Incorrect 17 ms 5620 KB wrong parameter
13 Incorrect 56 ms 6364 KB wrong parameter
14 Incorrect 20 ms 5620 KB wrong parameter
15 Incorrect 18 ms 5740 KB wrong parameter
16 Incorrect 37 ms 6244 KB wrong parameter
17 Incorrect 49 ms 6052 KB wrong parameter
18 Incorrect 51 ms 6360 KB wrong parameter
19 Incorrect 28 ms 5996 KB wrong parameter
20 Incorrect 64 ms 6660 KB wrong parameter
21 Incorrect 61 ms 6788 KB wrong parameter
22 Incorrect 49 ms 6240 KB wrong parameter
23 Incorrect 83 ms 6968 KB wrong parameter