oj.uz

Submission #965640

# Submission time Handle Problem Language Result Execution time Memory
965640 2024-04-19T03:25:03 Z fzyzzz_z Saveit (IOI10_saveit) C++17
50 / 100
 427 ms 23820 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 = nh - 1; i >= 0; --i) {
	// 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:69:8: warning: variable 'mx' set but not used [-Wunused-but-set-variable]
   69 |    int mx = 0;
      |        ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 21504 KB Output is correct - 37298 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 17776 KB Output is correct - 39794 call(s) of encode_bit()
4 Correct 2 ms 11516 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 252 ms 17836 KB Output is partially correct - 85895 call(s) of encode_bit()
6 Correct 307 ms 19600 KB Output is partially correct - 87514 call(s) of encode_bit()
7 Correct 322 ms 21180 KB Output is partially correct - 164635 call(s) of encode_bit()
8 Correct 299 ms 18640 KB Output is correct - 19929 call(s) of encode_bit()
9 Correct 323 ms 19696 KB Output is correct - 19490 call(s) of encode_bit()
10 Correct 323 ms 19288 KB Output is correct - 19039 call(s) of encode_bit()
11 Correct 329 ms 19612 KB Output is correct - 35413 call(s) of encode_bit()
12 Correct 326 ms 19236 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 336 ms 21708 KB Output is partially correct - 94292 call(s) of encode_bit()
14 Correct 325 ms 19268 KB Output is correct - 22977 call(s) of encode_bit()
15 Correct 322 ms 19524 KB Output is correct - 26252 call(s) of encode_bit()
16 Correct 332 ms 19512 KB Output is correct - 43584 call(s) of encode_bit()
17 Correct 328 ms 19504 KB Output is correct - 31456 call(s) of encode_bit()
18 Correct 327 ms 19412 KB Output is correct - 54333 call(s) of encode_bit()
19 Correct 331 ms 19124 KB Output is correct - 67527 call(s) of encode_bit()
20 Correct 328 ms 21504 KB Output is correct - 64533 call(s) of encode_bit()
21 Correct 345 ms 21448 KB Output is correct - 66185 call(s) of encode_bit()
22 Correct 333 ms 21668 KB Output is partially correct - 135298 call(s) of encode_bit()
23 Correct 341 ms 23820 KB Output is partially correct - 97716 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 21504 KB Output is correct - 37298 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 17776 KB Output is correct - 39794 call(s) of encode_bit()
4 Correct 2 ms 11516 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 252 ms 17836 KB Output is partially correct - 85895 call(s) of encode_bit()
6 Correct 307 ms 19600 KB Output is partially correct - 87514 call(s) of encode_bit()
7 Correct 322 ms 21180 KB Output is partially correct - 164635 call(s) of encode_bit()
8 Correct 299 ms 18640 KB Output is correct - 19929 call(s) of encode_bit()
9 Correct 323 ms 19696 KB Output is correct - 19490 call(s) of encode_bit()
10 Correct 323 ms 19288 KB Output is correct - 19039 call(s) of encode_bit()
11 Correct 329 ms 19612 KB Output is correct - 35413 call(s) of encode_bit()
12 Correct 326 ms 19236 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 336 ms 21708 KB Output is partially correct - 94292 call(s) of encode_bit()
14 Correct 325 ms 19268 KB Output is correct - 22977 call(s) of encode_bit()
15 Correct 322 ms 19524 KB Output is correct - 26252 call(s) of encode_bit()
16 Correct 332 ms 19512 KB Output is correct - 43584 call(s) of encode_bit()
17 Correct 328 ms 19504 KB Output is correct - 31456 call(s) of encode_bit()
18 Correct 327 ms 19412 KB Output is correct - 54333 call(s) of encode_bit()
19 Correct 331 ms 19124 KB Output is correct - 67527 call(s) of encode_bit()
20 Correct 328 ms 21504 KB Output is correct - 64533 call(s) of encode_bit()
21 Correct 345 ms 21448 KB Output is correct - 66185 call(s) of encode_bit()
22 Correct 333 ms 21668 KB Output is partially correct - 135298 call(s) of encode_bit()
23 Correct 341 ms 23820 KB Output is partially correct - 97716 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 21504 KB Output is correct - 37298 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 17776 KB Output is correct - 39794 call(s) of encode_bit()
4 Correct 2 ms 11516 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 252 ms 17836 KB Output is partially correct - 85895 call(s) of encode_bit()
6 Correct 307 ms 19600 KB Output is partially correct - 87514 call(s) of encode_bit()
7 Correct 322 ms 21180 KB Output is partially correct - 164635 call(s) of encode_bit()
8 Correct 299 ms 18640 KB Output is correct - 19929 call(s) of encode_bit()
9 Correct 323 ms 19696 KB Output is correct - 19490 call(s) of encode_bit()
10 Correct 323 ms 19288 KB Output is correct - 19039 call(s) of encode_bit()
11 Correct 329 ms 19612 KB Output is correct - 35413 call(s) of encode_bit()
12 Correct 326 ms 19236 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 336 ms 21708 KB Output is partially correct - 94292 call(s) of encode_bit()
14 Correct 325 ms 19268 KB Output is correct - 22977 call(s) of encode_bit()
15 Correct 322 ms 19524 KB Output is correct - 26252 call(s) of encode_bit()
16 Correct 332 ms 19512 KB Output is correct - 43584 call(s) of encode_bit()
17 Correct 328 ms 19504 KB Output is correct - 31456 call(s) of encode_bit()
18 Correct 327 ms 19412 KB Output is correct - 54333 call(s) of encode_bit()
19 Correct 331 ms 19124 KB Output is correct - 67527 call(s) of encode_bit()
20 Correct 328 ms 21504 KB Output is correct - 64533 call(s) of encode_bit()
21 Correct 345 ms 21448 KB Output is correct - 66185 call(s) of encode_bit()
22 Correct 333 ms 21668 KB Output is partially correct - 135298 call(s) of encode_bit()
23 Correct 341 ms 23820 KB Output is partially correct - 97716 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 21504 KB Output is correct - 37298 call(s) of encode_bit()
2 Correct 2 ms 11264 KB Output is correct - 15 call(s) of encode_bit()
3 Correct 253 ms 17776 KB Output is correct - 39794 call(s) of encode_bit()
4 Correct 2 ms 11516 KB Output is correct - 16 call(s) of encode_bit()
5 Correct 252 ms 17836 KB Output is partially correct - 85895 call(s) of encode_bit()
6 Correct 307 ms 19600 KB Output is partially correct - 87514 call(s) of encode_bit()
7 Correct 322 ms 21180 KB Output is partially correct - 164635 call(s) of encode_bit()
8 Correct 299 ms 18640 KB Output is correct - 19929 call(s) of encode_bit()
9 Correct 323 ms 19696 KB Output is correct - 19490 call(s) of encode_bit()
10 Correct 323 ms 19288 KB Output is correct - 19039 call(s) of encode_bit()
11 Correct 329 ms 19612 KB Output is correct - 35413 call(s) of encode_bit()
12 Correct 326 ms 19236 KB Output is correct - 12989 call(s) of encode_bit()
13 Correct 336 ms 21708 KB Output is partially correct - 94292 call(s) of encode_bit()
14 Correct 325 ms 19268 KB Output is correct - 22977 call(s) of encode_bit()
15 Correct 322 ms 19524 KB Output is correct - 26252 call(s) of encode_bit()
16 Correct 332 ms 19512 KB Output is correct - 43584 call(s) of encode_bit()
17 Correct 328 ms 19504 KB Output is correct - 31456 call(s) of encode_bit()
18 Correct 327 ms 19412 KB Output is correct - 54333 call(s) of encode_bit()
19 Correct 331 ms 19124 KB Output is correct - 67527 call(s) of encode_bit()
20 Correct 328 ms 21504 KB Output is correct - 64533 call(s) of encode_bit()
21 Correct 345 ms 21448 KB Output is correct - 66185 call(s) of encode_bit()
22 Correct 333 ms 21668 KB Output is partially correct - 135298 call(s) of encode_bit()
23 Correct 341 ms 23820 KB Output is partially correct - 97716 call(s) of encode_bit()