oj.uz

Submission #965623

# Submission time Handle Problem Language Result Execution time Memory
965623 2024-04-19T03:18:56 Z fzyzzz_z Saveit (IOI10_saveit) C++17
0 / 100
 311 ms 32080 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); 
          	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 311 ms 21232 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB too many decode_bit() calls
3 Runtime error 176 ms 25440 KB Execution killed with signal 11
4 Incorrect 2 ms 11264 KB too many decode_bit() calls
5 Runtime error 181 ms 25468 KB Execution killed with signal 11
6 Runtime error 227 ms 27756 KB Execution killed with signal 11
7 Runtime error 237 ms 32080 KB Execution killed with signal 11
8 Runtime error 205 ms 27048 KB Execution killed with signal 11
9 Runtime error 227 ms 27564 KB Execution killed with signal 11
10 Incorrect 216 ms 19180 KB too many decode_bit() calls
11 Runtime error 229 ms 28000 KB Execution killed with signal 11
12 Incorrect 216 ms 19224 KB too many decode_bit() calls
13 Runtime error 240 ms 27868 KB Execution killed with signal 11
14 Runtime error 222 ms 21136 KB Execution killed with signal 11
15 Runtime error 222 ms 21168 KB Execution killed with signal 11
16 Runtime error 239 ms 21792 KB Execution killed with signal 11
17 Runtime error 230 ms 23388 KB Execution killed with signal 11
18 Runtime error 232 ms 23732 KB Execution killed with signal 11
19 Runtime error 231 ms 22096 KB Execution killed with signal 11
20 Runtime error 242 ms 22008 KB Execution killed with signal 11
21 Incorrect 237 ms 21184 KB too many decode_bit() calls
22 Runtime error 242 ms 31948 KB Execution killed with signal 11
23 Incorrect 241 ms 23560 KB too many decode_bit() calls

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 21232 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB too many decode_bit() calls
3 Runtime error 176 ms 25440 KB Execution killed with signal 11
4 Incorrect 2 ms 11264 KB too many decode_bit() calls
5 Runtime error 181 ms 25468 KB Execution killed with signal 11
6 Runtime error 227 ms 27756 KB Execution killed with signal 11
7 Runtime error 237 ms 32080 KB Execution killed with signal 11
8 Runtime error 205 ms 27048 KB Execution killed with signal 11
9 Runtime error 227 ms 27564 KB Execution killed with signal 11
10 Incorrect 216 ms 19180 KB too many decode_bit() calls
11 Runtime error 229 ms 28000 KB Execution killed with signal 11
12 Incorrect 216 ms 19224 KB too many decode_bit() calls
13 Runtime error 240 ms 27868 KB Execution killed with signal 11
14 Runtime error 222 ms 21136 KB Execution killed with signal 11
15 Runtime error 222 ms 21168 KB Execution killed with signal 11
16 Runtime error 239 ms 21792 KB Execution killed with signal 11
17 Runtime error 230 ms 23388 KB Execution killed with signal 11
18 Runtime error 232 ms 23732 KB Execution killed with signal 11
19 Runtime error 231 ms 22096 KB Execution killed with signal 11
20 Runtime error 242 ms 22008 KB Execution killed with signal 11
21 Incorrect 237 ms 21184 KB too many decode_bit() calls
22 Runtime error 242 ms 31948 KB Execution killed with signal 11
23 Incorrect 241 ms 23560 KB too many decode_bit() calls

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 21232 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB too many decode_bit() calls
3 Runtime error 176 ms 25440 KB Execution killed with signal 11
4 Incorrect 2 ms 11264 KB too many decode_bit() calls
5 Runtime error 181 ms 25468 KB Execution killed with signal 11
6 Runtime error 227 ms 27756 KB Execution killed with signal 11
7 Runtime error 237 ms 32080 KB Execution killed with signal 11
8 Runtime error 205 ms 27048 KB Execution killed with signal 11
9 Runtime error 227 ms 27564 KB Execution killed with signal 11
10 Incorrect 216 ms 19180 KB too many decode_bit() calls
11 Runtime error 229 ms 28000 KB Execution killed with signal 11
12 Incorrect 216 ms 19224 KB too many decode_bit() calls
13 Runtime error 240 ms 27868 KB Execution killed with signal 11
14 Runtime error 222 ms 21136 KB Execution killed with signal 11
15 Runtime error 222 ms 21168 KB Execution killed with signal 11
16 Runtime error 239 ms 21792 KB Execution killed with signal 11
17 Runtime error 230 ms 23388 KB Execution killed with signal 11
18 Runtime error 232 ms 23732 KB Execution killed with signal 11
19 Runtime error 231 ms 22096 KB Execution killed with signal 11
20 Runtime error 242 ms 22008 KB Execution killed with signal 11
21 Incorrect 237 ms 21184 KB too many decode_bit() calls
22 Runtime error 242 ms 31948 KB Execution killed with signal 11
23 Incorrect 241 ms 23560 KB too many decode_bit() calls

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 21232 KB too many decode_bit() calls
2 Incorrect 2 ms 11264 KB too many decode_bit() calls
3 Runtime error 176 ms 25440 KB Execution killed with signal 11
4 Incorrect 2 ms 11264 KB too many decode_bit() calls
5 Runtime error 181 ms 25468 KB Execution killed with signal 11
6 Runtime error 227 ms 27756 KB Execution killed with signal 11
7 Runtime error 237 ms 32080 KB Execution killed with signal 11
8 Runtime error 205 ms 27048 KB Execution killed with signal 11
9 Runtime error 227 ms 27564 KB Execution killed with signal 11
10 Incorrect 216 ms 19180 KB too many decode_bit() calls
11 Runtime error 229 ms 28000 KB Execution killed with signal 11
12 Incorrect 216 ms 19224 KB too many decode_bit() calls
13 Runtime error 240 ms 27868 KB Execution killed with signal 11
14 Runtime error 222 ms 21136 KB Execution killed with signal 11
15 Runtime error 222 ms 21168 KB Execution killed with signal 11
16 Runtime error 239 ms 21792 KB Execution killed with signal 11
17 Runtime error 230 ms 23388 KB Execution killed with signal 11
18 Runtime error 232 ms 23732 KB Execution killed with signal 11
19 Runtime error 231 ms 22096 KB Execution killed with signal 11
20 Runtime error 242 ms 22008 KB Execution killed with signal 11
21 Incorrect 237 ms 21184 KB too many decode_bit() calls
22 Runtime error 242 ms 31948 KB Execution killed with signal 11
23 Incorrect 241 ms 23560 KB too many decode_bit() calls