oj.uz

Submission #965617

# Submission time Handle Problem Language Result Execution time Memory
965617 2024-04-19T03:14:18 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 334 ms 34268 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; 
				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 334 ms 21424 KB too many decode_bit() calls
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 183 ms 25352 KB Execution killed with signal 11
4 Correct 2 ms 11260 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 180 ms 25732 KB Execution killed with signal 11
6 Runtime error 223 ms 28056 KB Execution killed with signal 11
7 Runtime error 235 ms 31912 KB Execution killed with signal 11
8 Runtime error 210 ms 26792 KB Execution killed with signal 11
9 Incorrect 221 ms 19116 KB too many decode_bit() calls
10 Incorrect 219 ms 18972 KB too many decode_bit() calls
11 Incorrect 223 ms 19092 KB too many decode_bit() calls
12 Runtime error 227 ms 27600 KB Execution killed with signal 11
13 Runtime error 228 ms 27916 KB Execution killed with signal 11
14 Incorrect 219 ms 19172 KB too many decode_bit() calls
15 Runtime error 228 ms 27440 KB Execution killed with signal 11
16 Runtime error 242 ms 28292 KB Execution killed with signal 11
17 Runtime error 231 ms 27524 KB Execution killed with signal 11
18 Runtime error 255 ms 28040 KB Execution killed with signal 11
19 Runtime error 231 ms 27716 KB Execution killed with signal 11
20 Runtime error 256 ms 29956 KB Execution killed with signal 11
21 Runtime error 244 ms 30180 KB Execution killed with signal 11
22 Runtime error 251 ms 32176 KB Execution killed with signal 11
23 Runtime error 258 ms 34268 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 334 ms 21424 KB too many decode_bit() calls
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 183 ms 25352 KB Execution killed with signal 11
4 Correct 2 ms 11260 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 180 ms 25732 KB Execution killed with signal 11
6 Runtime error 223 ms 28056 KB Execution killed with signal 11
7 Runtime error 235 ms 31912 KB Execution killed with signal 11
8 Runtime error 210 ms 26792 KB Execution killed with signal 11
9 Incorrect 221 ms 19116 KB too many decode_bit() calls
10 Incorrect 219 ms 18972 KB too many decode_bit() calls
11 Incorrect 223 ms 19092 KB too many decode_bit() calls
12 Runtime error 227 ms 27600 KB Execution killed with signal 11
13 Runtime error 228 ms 27916 KB Execution killed with signal 11
14 Incorrect 219 ms 19172 KB too many decode_bit() calls
15 Runtime error 228 ms 27440 KB Execution killed with signal 11
16 Runtime error 242 ms 28292 KB Execution killed with signal 11
17 Runtime error 231 ms 27524 KB Execution killed with signal 11
18 Runtime error 255 ms 28040 KB Execution killed with signal 11
19 Runtime error 231 ms 27716 KB Execution killed with signal 11
20 Runtime error 256 ms 29956 KB Execution killed with signal 11
21 Runtime error 244 ms 30180 KB Execution killed with signal 11
22 Runtime error 251 ms 32176 KB Execution killed with signal 11
23 Runtime error 258 ms 34268 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 334 ms 21424 KB too many decode_bit() calls
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 183 ms 25352 KB Execution killed with signal 11
4 Correct 2 ms 11260 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 180 ms 25732 KB Execution killed with signal 11
6 Runtime error 223 ms 28056 KB Execution killed with signal 11
7 Runtime error 235 ms 31912 KB Execution killed with signal 11
8 Runtime error 210 ms 26792 KB Execution killed with signal 11
9 Incorrect 221 ms 19116 KB too many decode_bit() calls
10 Incorrect 219 ms 18972 KB too many decode_bit() calls
11 Incorrect 223 ms 19092 KB too many decode_bit() calls
12 Runtime error 227 ms 27600 KB Execution killed with signal 11
13 Runtime error 228 ms 27916 KB Execution killed with signal 11
14 Incorrect 219 ms 19172 KB too many decode_bit() calls
15 Runtime error 228 ms 27440 KB Execution killed with signal 11
16 Runtime error 242 ms 28292 KB Execution killed with signal 11
17 Runtime error 231 ms 27524 KB Execution killed with signal 11
18 Runtime error 255 ms 28040 KB Execution killed with signal 11
19 Runtime error 231 ms 27716 KB Execution killed with signal 11
20 Runtime error 256 ms 29956 KB Execution killed with signal 11
21 Runtime error 244 ms 30180 KB Execution killed with signal 11
22 Runtime error 251 ms 32176 KB Execution killed with signal 11
23 Runtime error 258 ms 34268 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 334 ms 21424 KB too many decode_bit() calls
2 Correct 2 ms 11268 KB Output is correct - 15 call(s) of encode_bit()
3 Runtime error 183 ms 25352 KB Execution killed with signal 11
4 Correct 2 ms 11260 KB Output is correct - 16 call(s) of encode_bit()
5 Runtime error 180 ms 25732 KB Execution killed with signal 11
6 Runtime error 223 ms 28056 KB Execution killed with signal 11
7 Runtime error 235 ms 31912 KB Execution killed with signal 11
8 Runtime error 210 ms 26792 KB Execution killed with signal 11
9 Incorrect 221 ms 19116 KB too many decode_bit() calls
10 Incorrect 219 ms 18972 KB too many decode_bit() calls
11 Incorrect 223 ms 19092 KB too many decode_bit() calls
12 Runtime error 227 ms 27600 KB Execution killed with signal 11
13 Runtime error 228 ms 27916 KB Execution killed with signal 11
14 Incorrect 219 ms 19172 KB too many decode_bit() calls
15 Runtime error 228 ms 27440 KB Execution killed with signal 11
16 Runtime error 242 ms 28292 KB Execution killed with signal 11
17 Runtime error 231 ms 27524 KB Execution killed with signal 11
18 Runtime error 255 ms 28040 KB Execution killed with signal 11
19 Runtime error 231 ms 27716 KB Execution killed with signal 11
20 Runtime error 256 ms 29956 KB Execution killed with signal 11
21 Runtime error 244 ms 30180 KB Execution killed with signal 11
22 Runtime error 251 ms 32176 KB Execution killed with signal 11
23 Runtime error 258 ms 34268 KB Execution killed with signal 11