oj.uz

Submission #676668

# Submission time Handle Problem Language Result Execution time Memory
676668 2022-12-31T16:02:34 Z nvujica Saveit (IOI10_saveit) C++14
0 / 100
 195 ms 10468 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];
int par[maxn];

void rek(int x, int p){
	bio[x] = 1;
	par[x] = p;
	
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		if(bio[x2]) continue;
		
		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);
	
	for(int i = 1; i < n; i++){
		ll b3 = 0;
		
		for(int j = 0; j < h; j++){
			b3 *= 3;
			
			if(dist[j][i] - dist[j][par[i]] == 1) b3 += 1;
			else if(dist[j][i] - dist[j][par[i]] == -1) b3 += 2; 
		}
		
		for(int j = 9; j >= 0; j--){
			if(par[i] & (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);
		}
	}
}
#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:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < v[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for(int j = 0; j < v[x].size(); j++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 10468 KB wrong parameter
2 Incorrect 2 ms 4732 KB wrong parameter
3 Incorrect 16 ms 5584 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 23 ms 5692 KB wrong parameter
6 Incorrect 19 ms 5876 KB wrong parameter
7 Incorrect 38 ms 6136 KB wrong parameter
8 Incorrect 16 ms 5620 KB wrong parameter
9 Incorrect 18 ms 5616 KB wrong parameter
10 Incorrect 18 ms 5684 KB wrong parameter
11 Incorrect 22 ms 5816 KB wrong parameter
12 Incorrect 20 ms 5532 KB wrong parameter
13 Incorrect 40 ms 6356 KB wrong parameter
14 Incorrect 17 ms 5620 KB wrong parameter
15 Incorrect 20 ms 5736 KB wrong parameter
16 Incorrect 39 ms 6092 KB wrong parameter
17 Incorrect 33 ms 6148 KB wrong parameter
18 Incorrect 40 ms 6380 KB wrong parameter
19 Incorrect 27 ms 5912 KB wrong parameter
20 Incorrect 56 ms 6728 KB wrong parameter
21 Incorrect 88 ms 6792 KB wrong parameter
22 Incorrect 41 ms 6252 KB wrong parameter
23 Incorrect 87 ms 6920 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 10468 KB wrong parameter
2 Incorrect 2 ms 4732 KB wrong parameter
3 Incorrect 16 ms 5584 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 23 ms 5692 KB wrong parameter
6 Incorrect 19 ms 5876 KB wrong parameter
7 Incorrect 38 ms 6136 KB wrong parameter
8 Incorrect 16 ms 5620 KB wrong parameter
9 Incorrect 18 ms 5616 KB wrong parameter
10 Incorrect 18 ms 5684 KB wrong parameter
11 Incorrect 22 ms 5816 KB wrong parameter
12 Incorrect 20 ms 5532 KB wrong parameter
13 Incorrect 40 ms 6356 KB wrong parameter
14 Incorrect 17 ms 5620 KB wrong parameter
15 Incorrect 20 ms 5736 KB wrong parameter
16 Incorrect 39 ms 6092 KB wrong parameter
17 Incorrect 33 ms 6148 KB wrong parameter
18 Incorrect 40 ms 6380 KB wrong parameter
19 Incorrect 27 ms 5912 KB wrong parameter
20 Incorrect 56 ms 6728 KB wrong parameter
21 Incorrect 88 ms 6792 KB wrong parameter
22 Incorrect 41 ms 6252 KB wrong parameter
23 Incorrect 87 ms 6920 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 10468 KB wrong parameter
2 Incorrect 2 ms 4732 KB wrong parameter
3 Incorrect 16 ms 5584 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 23 ms 5692 KB wrong parameter
6 Incorrect 19 ms 5876 KB wrong parameter
7 Incorrect 38 ms 6136 KB wrong parameter
8 Incorrect 16 ms 5620 KB wrong parameter
9 Incorrect 18 ms 5616 KB wrong parameter
10 Incorrect 18 ms 5684 KB wrong parameter
11 Incorrect 22 ms 5816 KB wrong parameter
12 Incorrect 20 ms 5532 KB wrong parameter
13 Incorrect 40 ms 6356 KB wrong parameter
14 Incorrect 17 ms 5620 KB wrong parameter
15 Incorrect 20 ms 5736 KB wrong parameter
16 Incorrect 39 ms 6092 KB wrong parameter
17 Incorrect 33 ms 6148 KB wrong parameter
18 Incorrect 40 ms 6380 KB wrong parameter
19 Incorrect 27 ms 5912 KB wrong parameter
20 Incorrect 56 ms 6728 KB wrong parameter
21 Incorrect 88 ms 6792 KB wrong parameter
22 Incorrect 41 ms 6252 KB wrong parameter
23 Incorrect 87 ms 6920 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 10468 KB wrong parameter
2 Incorrect 2 ms 4732 KB wrong parameter
3 Incorrect 16 ms 5584 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 23 ms 5692 KB wrong parameter
6 Incorrect 19 ms 5876 KB wrong parameter
7 Incorrect 38 ms 6136 KB wrong parameter
8 Incorrect 16 ms 5620 KB wrong parameter
9 Incorrect 18 ms 5616 KB wrong parameter
10 Incorrect 18 ms 5684 KB wrong parameter
11 Incorrect 22 ms 5816 KB wrong parameter
12 Incorrect 20 ms 5532 KB wrong parameter
13 Incorrect 40 ms 6356 KB wrong parameter
14 Incorrect 17 ms 5620 KB wrong parameter
15 Incorrect 20 ms 5736 KB wrong parameter
16 Incorrect 39 ms 6092 KB wrong parameter
17 Incorrect 33 ms 6148 KB wrong parameter
18 Incorrect 40 ms 6380 KB wrong parameter
19 Incorrect 27 ms 5912 KB wrong parameter
20 Incorrect 56 ms 6728 KB wrong parameter
21 Incorrect 88 ms 6792 KB wrong parameter
22 Incorrect 41 ms 6252 KB wrong parameter
23 Incorrect 87 ms 6920 KB wrong parameter