oj.uz

Submission #965612

# Submission time Handle Problem Language Result Execution time Memory
965612 2024-04-19T03:09:28 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 374 ms 33940 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) {
					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 374 ms 21460 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB Output isn't correct
3 Runtime error 176 ms 25436 KB Execution killed with signal 11
4 Incorrect 3 ms 11268 KB Output isn't correct
5 Runtime error 183 ms 25480 KB Execution killed with signal 11
6 Runtime error 217 ms 27764 KB Execution killed with signal 11
7 Runtime error 250 ms 32132 KB Execution killed with signal 11
8 Runtime error 210 ms 26796 KB Execution killed with signal 11
9 Incorrect 220 ms 19164 KB too many decode_bit() calls
10 Incorrect 220 ms 19392 KB too many decode_bit() calls
11 Incorrect 221 ms 19244 KB too many decode_bit() calls
12 Runtime error 229 ms 27616 KB Execution killed with signal 11
13 Runtime error 230 ms 28028 KB Execution killed with signal 11
14 Incorrect 219 ms 19212 KB too many decode_bit() calls
15 Runtime error 229 ms 27640 KB Execution killed with signal 11
16 Runtime error 242 ms 27896 KB Execution killed with signal 11
17 Runtime error 234 ms 27936 KB Execution killed with signal 11
18 Runtime error 243 ms 28324 KB Execution killed with signal 11
19 Runtime error 229 ms 27820 KB Execution killed with signal 11
20 Runtime error 237 ms 29972 KB Execution killed with signal 11
21 Runtime error 255 ms 29968 KB Execution killed with signal 11
22 Runtime error 246 ms 31936 KB Execution killed with signal 11
23 Runtime error 240 ms 33940 KB Execution killed with signal 11

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 21460 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB Output isn't correct
3 Runtime error 176 ms 25436 KB Execution killed with signal 11
4 Incorrect 3 ms 11268 KB Output isn't correct
5 Runtime error 183 ms 25480 KB Execution killed with signal 11
6 Runtime error 217 ms 27764 KB Execution killed with signal 11
7 Runtime error 250 ms 32132 KB Execution killed with signal 11
8 Runtime error 210 ms 26796 KB Execution killed with signal 11
9 Incorrect 220 ms 19164 KB too many decode_bit() calls
10 Incorrect 220 ms 19392 KB too many decode_bit() calls
11 Incorrect 221 ms 19244 KB too many decode_bit() calls
12 Runtime error 229 ms 27616 KB Execution killed with signal 11
13 Runtime error 230 ms 28028 KB Execution killed with signal 11
14 Incorrect 219 ms 19212 KB too many decode_bit() calls
15 Runtime error 229 ms 27640 KB Execution killed with signal 11
16 Runtime error 242 ms 27896 KB Execution killed with signal 11
17 Runtime error 234 ms 27936 KB Execution killed with signal 11
18 Runtime error 243 ms 28324 KB Execution killed with signal 11
19 Runtime error 229 ms 27820 KB Execution killed with signal 11
20 Runtime error 237 ms 29972 KB Execution killed with signal 11
21 Runtime error 255 ms 29968 KB Execution killed with signal 11
22 Runtime error 246 ms 31936 KB Execution killed with signal 11
23 Runtime error 240 ms 33940 KB Execution killed with signal 11

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 21460 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB Output isn't correct
3 Runtime error 176 ms 25436 KB Execution killed with signal 11
4 Incorrect 3 ms 11268 KB Output isn't correct
5 Runtime error 183 ms 25480 KB Execution killed with signal 11
6 Runtime error 217 ms 27764 KB Execution killed with signal 11
7 Runtime error 250 ms 32132 KB Execution killed with signal 11
8 Runtime error 210 ms 26796 KB Execution killed with signal 11
9 Incorrect 220 ms 19164 KB too many decode_bit() calls
10 Incorrect 220 ms 19392 KB too many decode_bit() calls
11 Incorrect 221 ms 19244 KB too many decode_bit() calls
12 Runtime error 229 ms 27616 KB Execution killed with signal 11
13 Runtime error 230 ms 28028 KB Execution killed with signal 11
14 Incorrect 219 ms 19212 KB too many decode_bit() calls
15 Runtime error 229 ms 27640 KB Execution killed with signal 11
16 Runtime error 242 ms 27896 KB Execution killed with signal 11
17 Runtime error 234 ms 27936 KB Execution killed with signal 11
18 Runtime error 243 ms 28324 KB Execution killed with signal 11
19 Runtime error 229 ms 27820 KB Execution killed with signal 11
20 Runtime error 237 ms 29972 KB Execution killed with signal 11
21 Runtime error 255 ms 29968 KB Execution killed with signal 11
22 Runtime error 246 ms 31936 KB Execution killed with signal 11
23 Runtime error 240 ms 33940 KB Execution killed with signal 11

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 21460 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB Output isn't correct
3 Runtime error 176 ms 25436 KB Execution killed with signal 11
4 Incorrect 3 ms 11268 KB Output isn't correct
5 Runtime error 183 ms 25480 KB Execution killed with signal 11
6 Runtime error 217 ms 27764 KB Execution killed with signal 11
7 Runtime error 250 ms 32132 KB Execution killed with signal 11
8 Runtime error 210 ms 26796 KB Execution killed with signal 11
9 Incorrect 220 ms 19164 KB too many decode_bit() calls
10 Incorrect 220 ms 19392 KB too many decode_bit() calls
11 Incorrect 221 ms 19244 KB too many decode_bit() calls
12 Runtime error 229 ms 27616 KB Execution killed with signal 11
13 Runtime error 230 ms 28028 KB Execution killed with signal 11
14 Incorrect 219 ms 19212 KB too many decode_bit() calls
15 Runtime error 229 ms 27640 KB Execution killed with signal 11
16 Runtime error 242 ms 27896 KB Execution killed with signal 11
17 Runtime error 234 ms 27936 KB Execution killed with signal 11
18 Runtime error 243 ms 28324 KB Execution killed with signal 11
19 Runtime error 229 ms 27820 KB Execution killed with signal 11
20 Runtime error 237 ms 29972 KB Execution killed with signal 11
21 Runtime error 255 ms 29968 KB Execution killed with signal 11
22 Runtime error 246 ms 31936 KB Execution killed with signal 11
23 Runtime error 240 ms 33940 KB Execution killed with signal 11