oj.uz

Submission #676730

# Submission time Handle Problem Language Result Execution time Memory
676730 2022-12-31T20:53:06 Z nvujica Saveit (IOI10_saveit) C++14
0 / 100
 254 ms 10672 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];
int d[maxn][maxh];
vector <int> v[maxn];

void rek(int x, int h){
	for(int i = 0; i < v[x].size(); i++){
		int x2 = v[x][i];
		
		for(int j = 0; j < h; j++){
			dist[j][x2] = dist[j][x] + d[x2][j];
		}
		
		rek(x2, h);
	}
}

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();
		}
		
		v[p].push_back(i);
		
		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 == 1) d[i][j] = 1;
			if(x == 2) d[i][j] = -1;
			
			b3 /= 3;
		}
	}
	
	rek(0, h);
	
	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++){
      |                   ~~^~~~~~~~~~~~~

decoder.cpp: In function 'void rek(int, int)':
decoder.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++){
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 254 ms 10672 KB wrong parameter
2 Incorrect 3 ms 4740 KB wrong parameter
3 Incorrect 17 ms 5916 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 20 ms 6056 KB wrong parameter
6 Incorrect 25 ms 5992 KB wrong parameter
7 Incorrect 34 ms 6336 KB wrong parameter
8 Incorrect 15 ms 5892 KB wrong parameter
9 Incorrect 17 ms 5872 KB wrong parameter
10 Incorrect 20 ms 5820 KB wrong parameter
11 Incorrect 19 ms 6080 KB wrong parameter
12 Incorrect 17 ms 5832 KB wrong parameter
13 Incorrect 41 ms 6508 KB wrong parameter
14 Incorrect 17 ms 5976 KB wrong parameter
15 Incorrect 17 ms 6012 KB wrong parameter
16 Incorrect 38 ms 6292 KB wrong parameter
17 Incorrect 33 ms 6416 KB wrong parameter
18 Incorrect 43 ms 6696 KB wrong parameter
19 Incorrect 32 ms 6220 KB wrong parameter
20 Incorrect 52 ms 6988 KB wrong parameter
21 Incorrect 59 ms 7004 KB wrong parameter
22 Incorrect 42 ms 6568 KB wrong parameter
23 Incorrect 67 ms 7256 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 254 ms 10672 KB wrong parameter
2 Incorrect 3 ms 4740 KB wrong parameter
3 Incorrect 17 ms 5916 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 20 ms 6056 KB wrong parameter
6 Incorrect 25 ms 5992 KB wrong parameter
7 Incorrect 34 ms 6336 KB wrong parameter
8 Incorrect 15 ms 5892 KB wrong parameter
9 Incorrect 17 ms 5872 KB wrong parameter
10 Incorrect 20 ms 5820 KB wrong parameter
11 Incorrect 19 ms 6080 KB wrong parameter
12 Incorrect 17 ms 5832 KB wrong parameter
13 Incorrect 41 ms 6508 KB wrong parameter
14 Incorrect 17 ms 5976 KB wrong parameter
15 Incorrect 17 ms 6012 KB wrong parameter
16 Incorrect 38 ms 6292 KB wrong parameter
17 Incorrect 33 ms 6416 KB wrong parameter
18 Incorrect 43 ms 6696 KB wrong parameter
19 Incorrect 32 ms 6220 KB wrong parameter
20 Incorrect 52 ms 6988 KB wrong parameter
21 Incorrect 59 ms 7004 KB wrong parameter
22 Incorrect 42 ms 6568 KB wrong parameter
23 Incorrect 67 ms 7256 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 254 ms 10672 KB wrong parameter
2 Incorrect 3 ms 4740 KB wrong parameter
3 Incorrect 17 ms 5916 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 20 ms 6056 KB wrong parameter
6 Incorrect 25 ms 5992 KB wrong parameter
7 Incorrect 34 ms 6336 KB wrong parameter
8 Incorrect 15 ms 5892 KB wrong parameter
9 Incorrect 17 ms 5872 KB wrong parameter
10 Incorrect 20 ms 5820 KB wrong parameter
11 Incorrect 19 ms 6080 KB wrong parameter
12 Incorrect 17 ms 5832 KB wrong parameter
13 Incorrect 41 ms 6508 KB wrong parameter
14 Incorrect 17 ms 5976 KB wrong parameter
15 Incorrect 17 ms 6012 KB wrong parameter
16 Incorrect 38 ms 6292 KB wrong parameter
17 Incorrect 33 ms 6416 KB wrong parameter
18 Incorrect 43 ms 6696 KB wrong parameter
19 Incorrect 32 ms 6220 KB wrong parameter
20 Incorrect 52 ms 6988 KB wrong parameter
21 Incorrect 59 ms 7004 KB wrong parameter
22 Incorrect 42 ms 6568 KB wrong parameter
23 Incorrect 67 ms 7256 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 254 ms 10672 KB wrong parameter
2 Incorrect 3 ms 4740 KB wrong parameter
3 Incorrect 17 ms 5916 KB wrong parameter
4 Incorrect 2 ms 4732 KB wrong parameter
5 Incorrect 20 ms 6056 KB wrong parameter
6 Incorrect 25 ms 5992 KB wrong parameter
7 Incorrect 34 ms 6336 KB wrong parameter
8 Incorrect 15 ms 5892 KB wrong parameter
9 Incorrect 17 ms 5872 KB wrong parameter
10 Incorrect 20 ms 5820 KB wrong parameter
11 Incorrect 19 ms 6080 KB wrong parameter
12 Incorrect 17 ms 5832 KB wrong parameter
13 Incorrect 41 ms 6508 KB wrong parameter
14 Incorrect 17 ms 5976 KB wrong parameter
15 Incorrect 17 ms 6012 KB wrong parameter
16 Incorrect 38 ms 6292 KB wrong parameter
17 Incorrect 33 ms 6416 KB wrong parameter
18 Incorrect 43 ms 6696 KB wrong parameter
19 Incorrect 32 ms 6220 KB wrong parameter
20 Incorrect 52 ms 6988 KB wrong parameter
21 Incorrect 59 ms 7004 KB wrong parameter
22 Incorrect 42 ms 6568 KB wrong parameter
23 Incorrect 67 ms 7256 KB wrong parameter