oj.uz

Submission #965637

# Submission time Handle Problem Language Result Execution time Memory
965637 2024-04-19T03:23:26 Z fzyzzz_z Saveit (IOI10_saveit) C++17
50 / 100
 416 ms 23536 KB 
#include <bits/stdc++.h>
using namespace std; 

#include "grader.h"
#include "encoder.h"

// vector<int> bits; 
// void encode_bit(int x) { bits.push_back(x); }

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); 
				}
			}
			encode_bit(0); 
		}
	}



	return;
}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	int n, k, p; 
// 	cin >> n >> k >> p; 
// 	int a[p], b[p]; 
// 	for (int i = 0; i < p; ++i) cin >> a[i] >> b[i]; 

// 	encode(n, k, p, a, b); 
// 	for (int i = 0; i < bits.size(); ++i) cout << bits[i]; 
// 	cout << '\n';

// 	return 0; 
// }



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

// string ss; 
// int decode_bit() { char c = ss.back(); ss.pop_back(); return c != '0'; } 
// void hops(int k, int i, int d) {
// 	cout << k << ' ' << i << ' ' << d << '\n';
// }

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; 
					// cout << "! " << i << ' ' << j << '\n';
				}
			}
		} 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; 
				// cout << "! " << i << ' ' << x << '\n';
			}
		}
	}

	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]); 
		}
	}
}

// int main() {
// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0); 

// 	int n, k; 
// 	cin >> n >> k; 
// 	cin >> ss; 
// 	reverse(ss.begin(), ss.end()); 
	
// 	decode(n, k); 

// 	return 0; 
// }

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:68:8: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   68 |    int mx = 0;
      |        ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 21500 KB Output is correct - 39905 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 18008 KB Output is correct - 39838 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 253 ms 17816 KB Output is partially correct - 85279 call(s) of encode_bit()
6 Correct 314 ms 19328 KB Output is partially correct - 88086 call(s) of encode_bit()
7 Correct 323 ms 21396 KB Output is partially correct - 166318 call(s) of encode_bit()
8 Correct 303 ms 18648 KB Output is correct - 19478 call(s) of encode_bit()
9 Correct 326 ms 19248 KB Output is correct - 19303 call(s) of encode_bit()
10 Correct 325 ms 19164 KB Output is correct - 18896 call(s) of encode_bit()
11 Correct 324 ms 19280 KB Output is correct - 35688 call(s) of encode_bit()
12 Correct 328 ms 19524 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 319 ms 21448 KB Output is partially correct - 93687 call(s) of encode_bit()
14 Correct 327 ms 19516 KB Output is correct - 23153 call(s) of encode_bit()
15 Correct 326 ms 19276 KB Output is correct - 25790 call(s) of encode_bit()
16 Correct 340 ms 19392 KB Output is correct - 44262 call(s) of encode_bit()
17 Correct 333 ms 19400 KB Output is correct - 31379 call(s) of encode_bit()
18 Correct 332 ms 19416 KB Output is correct - 53046 call(s) of encode_bit()
19 Correct 333 ms 19332 KB Output is correct - 68308 call(s) of encode_bit()
20 Correct 336 ms 21480 KB Output is correct - 65180 call(s) of encode_bit()
21 Correct 354 ms 21256 KB Output is correct - 63200 call(s) of encode_bit()
22 Correct 325 ms 21660 KB Output is partially correct - 134000 call(s) of encode_bit()
23 Correct 333 ms 23536 KB Output is partially correct - 97214 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 21500 KB Output is correct - 39905 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 18008 KB Output is correct - 39838 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 253 ms 17816 KB Output is partially correct - 85279 call(s) of encode_bit()
6 Correct 314 ms 19328 KB Output is partially correct - 88086 call(s) of encode_bit()
7 Correct 323 ms 21396 KB Output is partially correct - 166318 call(s) of encode_bit()
8 Correct 303 ms 18648 KB Output is correct - 19478 call(s) of encode_bit()
9 Correct 326 ms 19248 KB Output is correct - 19303 call(s) of encode_bit()
10 Correct 325 ms 19164 KB Output is correct - 18896 call(s) of encode_bit()
11 Correct 324 ms 19280 KB Output is correct - 35688 call(s) of encode_bit()
12 Correct 328 ms 19524 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 319 ms 21448 KB Output is partially correct - 93687 call(s) of encode_bit()
14 Correct 327 ms 19516 KB Output is correct - 23153 call(s) of encode_bit()
15 Correct 326 ms 19276 KB Output is correct - 25790 call(s) of encode_bit()
16 Correct 340 ms 19392 KB Output is correct - 44262 call(s) of encode_bit()
17 Correct 333 ms 19400 KB Output is correct - 31379 call(s) of encode_bit()
18 Correct 332 ms 19416 KB Output is correct - 53046 call(s) of encode_bit()
19 Correct 333 ms 19332 KB Output is correct - 68308 call(s) of encode_bit()
20 Correct 336 ms 21480 KB Output is correct - 65180 call(s) of encode_bit()
21 Correct 354 ms 21256 KB Output is correct - 63200 call(s) of encode_bit()
22 Correct 325 ms 21660 KB Output is partially correct - 134000 call(s) of encode_bit()
23 Correct 333 ms 23536 KB Output is partially correct - 97214 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 21500 KB Output is correct - 39905 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 18008 KB Output is correct - 39838 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 253 ms 17816 KB Output is partially correct - 85279 call(s) of encode_bit()
6 Correct 314 ms 19328 KB Output is partially correct - 88086 call(s) of encode_bit()
7 Correct 323 ms 21396 KB Output is partially correct - 166318 call(s) of encode_bit()
8 Correct 303 ms 18648 KB Output is correct - 19478 call(s) of encode_bit()
9 Correct 326 ms 19248 KB Output is correct - 19303 call(s) of encode_bit()
10 Correct 325 ms 19164 KB Output is correct - 18896 call(s) of encode_bit()
11 Correct 324 ms 19280 KB Output is correct - 35688 call(s) of encode_bit()
12 Correct 328 ms 19524 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 319 ms 21448 KB Output is partially correct - 93687 call(s) of encode_bit()
14 Correct 327 ms 19516 KB Output is correct - 23153 call(s) of encode_bit()
15 Correct 326 ms 19276 KB Output is correct - 25790 call(s) of encode_bit()
16 Correct 340 ms 19392 KB Output is correct - 44262 call(s) of encode_bit()
17 Correct 333 ms 19400 KB Output is correct - 31379 call(s) of encode_bit()
18 Correct 332 ms 19416 KB Output is correct - 53046 call(s) of encode_bit()
19 Correct 333 ms 19332 KB Output is correct - 68308 call(s) of encode_bit()
20 Correct 336 ms 21480 KB Output is correct - 65180 call(s) of encode_bit()
21 Correct 354 ms 21256 KB Output is correct - 63200 call(s) of encode_bit()
22 Correct 325 ms 21660 KB Output is partially correct - 134000 call(s) of encode_bit()
23 Correct 333 ms 23536 KB Output is partially correct - 97214 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 21500 KB Output is correct - 39905 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 18008 KB Output is correct - 39838 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 253 ms 17816 KB Output is partially correct - 85279 call(s) of encode_bit()
6 Correct 314 ms 19328 KB Output is partially correct - 88086 call(s) of encode_bit()
7 Correct 323 ms 21396 KB Output is partially correct - 166318 call(s) of encode_bit()
8 Correct 303 ms 18648 KB Output is correct - 19478 call(s) of encode_bit()
9 Correct 326 ms 19248 KB Output is correct - 19303 call(s) of encode_bit()
10 Correct 325 ms 19164 KB Output is correct - 18896 call(s) of encode_bit()
11 Correct 324 ms 19280 KB Output is correct - 35688 call(s) of encode_bit()
12 Correct 328 ms 19524 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 319 ms 21448 KB Output is partially correct - 93687 call(s) of encode_bit()
14 Correct 327 ms 19516 KB Output is correct - 23153 call(s) of encode_bit()
15 Correct 326 ms 19276 KB Output is correct - 25790 call(s) of encode_bit()
16 Correct 340 ms 19392 KB Output is correct - 44262 call(s) of encode_bit()
17 Correct 333 ms 19400 KB Output is correct - 31379 call(s) of encode_bit()
18 Correct 332 ms 19416 KB Output is correct - 53046 call(s) of encode_bit()
19 Correct 333 ms 19332 KB Output is correct - 68308 call(s) of encode_bit()
20 Correct 336 ms 21480 KB Output is correct - 65180 call(s) of encode_bit()
21 Correct 354 ms 21256 KB Output is correct - 63200 call(s) of encode_bit()
22 Correct 325 ms 21660 KB Output is partially correct - 134000 call(s) of encode_bit()
23 Correct 333 ms 23536 KB Output is partially correct - 97214 call(s) of encode_bit()