oj.uz

Submission #676657

# Submission time Handle Problem Language Result Execution time Memory
676657 2022-12-31T15:42:58 Z nvujica Saveit (IOI10_saveit) C++14
0 / 100
 267 ms 10464 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 = 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);
	}
}

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);
}
#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 267 ms 10464 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 15 ms 5548 KB wrong parameter
4 Incorrect 2 ms 4740 KB Output isn't correct
5 Incorrect 20 ms 5824 KB wrong parameter
6 Incorrect 20 ms 5836 KB wrong parameter
7 Incorrect 34 ms 6228 KB wrong parameter
8 Incorrect 15 ms 5596 KB wrong parameter
9 Incorrect 21 ms 5616 KB wrong parameter
10 Incorrect 16 ms 5628 KB wrong parameter
11 Incorrect 20 ms 5700 KB wrong parameter
12 Incorrect 16 ms 5672 KB wrong parameter
13 Incorrect 40 ms 6296 KB wrong parameter
14 Incorrect 16 ms 5744 KB wrong parameter
15 Incorrect 16 ms 5736 KB wrong parameter
16 Incorrect 36 ms 6236 KB wrong parameter
17 Incorrect 35 ms 6252 KB wrong parameter
18 Incorrect 47 ms 6308 KB wrong parameter
19 Incorrect 28 ms 5968 KB wrong parameter
20 Incorrect 55 ms 6716 KB wrong parameter
21 Incorrect 57 ms 6764 KB wrong parameter
22 Incorrect 38 ms 6308 KB wrong parameter
23 Incorrect 66 ms 7064 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10464 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 15 ms 5548 KB wrong parameter
4 Incorrect 2 ms 4740 KB Output isn't correct
5 Incorrect 20 ms 5824 KB wrong parameter
6 Incorrect 20 ms 5836 KB wrong parameter
7 Incorrect 34 ms 6228 KB wrong parameter
8 Incorrect 15 ms 5596 KB wrong parameter
9 Incorrect 21 ms 5616 KB wrong parameter
10 Incorrect 16 ms 5628 KB wrong parameter
11 Incorrect 20 ms 5700 KB wrong parameter
12 Incorrect 16 ms 5672 KB wrong parameter
13 Incorrect 40 ms 6296 KB wrong parameter
14 Incorrect 16 ms 5744 KB wrong parameter
15 Incorrect 16 ms 5736 KB wrong parameter
16 Incorrect 36 ms 6236 KB wrong parameter
17 Incorrect 35 ms 6252 KB wrong parameter
18 Incorrect 47 ms 6308 KB wrong parameter
19 Incorrect 28 ms 5968 KB wrong parameter
20 Incorrect 55 ms 6716 KB wrong parameter
21 Incorrect 57 ms 6764 KB wrong parameter
22 Incorrect 38 ms 6308 KB wrong parameter
23 Incorrect 66 ms 7064 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10464 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 15 ms 5548 KB wrong parameter
4 Incorrect 2 ms 4740 KB Output isn't correct
5 Incorrect 20 ms 5824 KB wrong parameter
6 Incorrect 20 ms 5836 KB wrong parameter
7 Incorrect 34 ms 6228 KB wrong parameter
8 Incorrect 15 ms 5596 KB wrong parameter
9 Incorrect 21 ms 5616 KB wrong parameter
10 Incorrect 16 ms 5628 KB wrong parameter
11 Incorrect 20 ms 5700 KB wrong parameter
12 Incorrect 16 ms 5672 KB wrong parameter
13 Incorrect 40 ms 6296 KB wrong parameter
14 Incorrect 16 ms 5744 KB wrong parameter
15 Incorrect 16 ms 5736 KB wrong parameter
16 Incorrect 36 ms 6236 KB wrong parameter
17 Incorrect 35 ms 6252 KB wrong parameter
18 Incorrect 47 ms 6308 KB wrong parameter
19 Incorrect 28 ms 5968 KB wrong parameter
20 Incorrect 55 ms 6716 KB wrong parameter
21 Incorrect 57 ms 6764 KB wrong parameter
22 Incorrect 38 ms 6308 KB wrong parameter
23 Incorrect 66 ms 7064 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 267 ms 10464 KB wrong parameter
2 Incorrect 3 ms 4732 KB Output isn't correct
3 Incorrect 15 ms 5548 KB wrong parameter
4 Incorrect 2 ms 4740 KB Output isn't correct
5 Incorrect 20 ms 5824 KB wrong parameter
6 Incorrect 20 ms 5836 KB wrong parameter
7 Incorrect 34 ms 6228 KB wrong parameter
8 Incorrect 15 ms 5596 KB wrong parameter
9 Incorrect 21 ms 5616 KB wrong parameter
10 Incorrect 16 ms 5628 KB wrong parameter
11 Incorrect 20 ms 5700 KB wrong parameter
12 Incorrect 16 ms 5672 KB wrong parameter
13 Incorrect 40 ms 6296 KB wrong parameter
14 Incorrect 16 ms 5744 KB wrong parameter
15 Incorrect 16 ms 5736 KB wrong parameter
16 Incorrect 36 ms 6236 KB wrong parameter
17 Incorrect 35 ms 6252 KB wrong parameter
18 Incorrect 47 ms 6308 KB wrong parameter
19 Incorrect 28 ms 5968 KB wrong parameter
20 Incorrect 55 ms 6716 KB wrong parameter
21 Incorrect 57 ms 6764 KB wrong parameter
22 Incorrect 38 ms 6308 KB wrong parameter
23 Incorrect 66 ms 7064 KB wrong parameter