oj.uz

Submission #965629

# Submission time Handle Problem Language Result Execution time Memory
965629 2024-04-19T03:20:52 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 305 ms 33976 KB 
#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>
using namespace std; 

void encode(int n, int nh, int ne, int *v1, int *v2){
	int g[n][n]; 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = 0; 
		}
	}
	for (int i = 0; i < ne; ++i) {
		g[v1[i]][v2[i]] = g[v2[i]][v1[i]] = 1; 
	}

	int inf = 1e9; 
	int d[nh][n]; 
	for (int i = 0; i < nh; ++i) {
		for (int j = 0; j < n; ++j) {
			d[i][j] = inf; 
		}
	}

	for (int i = 0; i < nh; ++i) {
		vector<int> c(1, i); 
		d[i][i] = 0; 

		for (int cd = 0; cd < n; ++cd) {
			vector<int> nc; 
			for (auto x: c) {
				for (int y = 0; y < n; ++y) {
					if (d[i][y] == inf && g[x][y] == 2) {
						d[i][y] = cd + 1; 
						nc.push_back(y); 
					}	
				}
			}
			for (auto x: c) {
				for (int y = 0; y < n; ++y) {
					if (d[i][y] == inf && g[x][y] == 1) {
						d[i][y] = cd + 1; 
						g[x][y] = g[y][x] = 2; 
						nc.push_back(y); 
					}	
				}
			}
			c = nc; 
		}
	}

	for (int i = 0; i < n; ++i) {
		int c = 0; 
		for (int j = i + 1; j < n; ++j) {
			c += g[i][j] == 2; 
		}
		if (n < c * 10) {
			encode_bit(0); 
			for (int j = i + 1; j < n; ++j) {
				encode_bit(g[i][j] == 2); 
			}
		} else {
			encode_bit(1); 
			int mx = 0; 
			for (int j = i + 1; j < n; ++j) if (g[i][j] == 2) mx = j; 
			for (int j = i + 1; j < n; ++j) {
				if (g[i][j] != 2) continue; 
				encode_bit(1); 
				for (int b = 0; b < 10; ++b) {
					encode_bit(((1 << b) & j) >> b); 
				}
				if (j < mx) encode_bit(1); 
			}
			encode_bit(0); 
		}
	}



	return;
}


#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;


void decode(int n, int nh) {
	int g[n][n]; 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = 0; 
		}
	}
	for (int i = 0; i < n; ++i) {
		int t = decode_bit(); 
		if (t == 0) {
			for (int j = i + 1; j < n; ++j) {
				if (decode_bit()) {
					g[i][j] = g[j][i] = 1; 
				}
			}
		} else {
			while (decode_bit()) {
				int x = 0; 
				for (int b = 0; b < 10; ++b) {
					x += (decode_bit() << b); 
				}
				g[i][x] = g[x][i] = 1; 
			}
		}
	}

	for (int k = 0; k < nh; ++k) {
		vector<int> d(n, 1e9); 
		d[k] = 0; 
		queue<int> q; 
		q.push(k); 
		while (!q.empty()) {
			auto x = q.front(); 
			q.pop(); 
			for (int y = 0; y < n; ++y) {
				if (y != x && d[y] > n && g[x][y]) {
					d[y] = d[x] + 1; 
					q.push(y); 
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			hops(k, i, d[i]); 
		}
	}
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 21388 KB too many decode_bit() calls
2 Correct 2 ms 11360 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 177 ms 25440 KB Execution killed with signal 11
4 Correct 8 ms 11264 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 181 ms 25476 KB Execution killed with signal 11
6 Runtime error 219 ms 32152 KB Execution killed with signal 11
7 Runtime error 242 ms 32160 KB Execution killed with signal 11
8 Runtime error 200 ms 26796 KB Execution killed with signal 11
9 Runtime error 218 ms 27624 KB Execution killed with signal 11
10 Runtime error 218 ms 27648 KB Execution killed with signal 11
11 Runtime error 219 ms 28004 KB Execution killed with signal 11
12 Incorrect 214 ms 19168 KB too many decode_bit() calls
13 Runtime error 229 ms 31964 KB Execution killed with signal 11
14 Runtime error 219 ms 27880 KB Execution killed with signal 11
15 Runtime error 223 ms 27668 KB Execution killed with signal 11
16 Runtime error 235 ms 27840 KB Execution killed with signal 11
17 Runtime error 223 ms 27776 KB Execution killed with signal 11
18 Runtime error 232 ms 27876 KB Execution killed with signal 11
19 Runtime error 227 ms 27948 KB Execution killed with signal 11
20 Runtime error 246 ms 29980 KB Execution killed with signal 11
21 Runtime error 239 ms 30084 KB Execution killed with signal 11
22 Runtime error 238 ms 31988 KB Execution killed with signal 11
23 Runtime error 247 ms 33976 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 21388 KB too many decode_bit() calls
2 Correct 2 ms 11360 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 177 ms 25440 KB Execution killed with signal 11
4 Correct 8 ms 11264 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 181 ms 25476 KB Execution killed with signal 11
6 Runtime error 219 ms 32152 KB Execution killed with signal 11
7 Runtime error 242 ms 32160 KB Execution killed with signal 11
8 Runtime error 200 ms 26796 KB Execution killed with signal 11
9 Runtime error 218 ms 27624 KB Execution killed with signal 11
10 Runtime error 218 ms 27648 KB Execution killed with signal 11
11 Runtime error 219 ms 28004 KB Execution killed with signal 11
12 Incorrect 214 ms 19168 KB too many decode_bit() calls
13 Runtime error 229 ms 31964 KB Execution killed with signal 11
14 Runtime error 219 ms 27880 KB Execution killed with signal 11
15 Runtime error 223 ms 27668 KB Execution killed with signal 11
16 Runtime error 235 ms 27840 KB Execution killed with signal 11
17 Runtime error 223 ms 27776 KB Execution killed with signal 11
18 Runtime error 232 ms 27876 KB Execution killed with signal 11
19 Runtime error 227 ms 27948 KB Execution killed with signal 11
20 Runtime error 246 ms 29980 KB Execution killed with signal 11
21 Runtime error 239 ms 30084 KB Execution killed with signal 11
22 Runtime error 238 ms 31988 KB Execution killed with signal 11
23 Runtime error 247 ms 33976 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 21388 KB too many decode_bit() calls
2 Correct 2 ms 11360 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 177 ms 25440 KB Execution killed with signal 11
4 Correct 8 ms 11264 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 181 ms 25476 KB Execution killed with signal 11
6 Runtime error 219 ms 32152 KB Execution killed with signal 11
7 Runtime error 242 ms 32160 KB Execution killed with signal 11
8 Runtime error 200 ms 26796 KB Execution killed with signal 11
9 Runtime error 218 ms 27624 KB Execution killed with signal 11
10 Runtime error 218 ms 27648 KB Execution killed with signal 11
11 Runtime error 219 ms 28004 KB Execution killed with signal 11
12 Incorrect 214 ms 19168 KB too many decode_bit() calls
13 Runtime error 229 ms 31964 KB Execution killed with signal 11
14 Runtime error 219 ms 27880 KB Execution killed with signal 11
15 Runtime error 223 ms 27668 KB Execution killed with signal 11
16 Runtime error 235 ms 27840 KB Execution killed with signal 11
17 Runtime error 223 ms 27776 KB Execution killed with signal 11
18 Runtime error 232 ms 27876 KB Execution killed with signal 11
19 Runtime error 227 ms 27948 KB Execution killed with signal 11
20 Runtime error 246 ms 29980 KB Execution killed with signal 11
21 Runtime error 239 ms 30084 KB Execution killed with signal 11
22 Runtime error 238 ms 31988 KB Execution killed with signal 11
23 Runtime error 247 ms 33976 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 305 ms 21388 KB too many decode_bit() calls
2 Correct 2 ms 11360 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 177 ms 25440 KB Execution killed with signal 11
4 Correct 8 ms 11264 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 181 ms 25476 KB Execution killed with signal 11
6 Runtime error 219 ms 32152 KB Execution killed with signal 11
7 Runtime error 242 ms 32160 KB Execution killed with signal 11
8 Runtime error 200 ms 26796 KB Execution killed with signal 11
9 Runtime error 218 ms 27624 KB Execution killed with signal 11
10 Runtime error 218 ms 27648 KB Execution killed with signal 11
11 Runtime error 219 ms 28004 KB Execution killed with signal 11
12 Incorrect 214 ms 19168 KB too many decode_bit() calls
13 Runtime error 229 ms 31964 KB Execution killed with signal 11
14 Runtime error 219 ms 27880 KB Execution killed with signal 11
15 Runtime error 223 ms 27668 KB Execution killed with signal 11
16 Runtime error 235 ms 27840 KB Execution killed with signal 11
17 Runtime error 223 ms 27776 KB Execution killed with signal 11
18 Runtime error 232 ms 27876 KB Execution killed with signal 11
19 Runtime error 227 ms 27948 KB Execution killed with signal 11
20 Runtime error 246 ms 29980 KB Execution killed with signal 11
21 Runtime error 239 ms 30084 KB Execution killed with signal 11
22 Runtime error 238 ms 31988 KB Execution killed with signal 11
23 Runtime error 247 ms 33976 KB Execution killed with signal 11