oj.uz

Submission #1029847

# Submission time Handle Problem Language Result Execution time Memory
1029847 2024-07-21T12:07:41 Z Tob Saveit (IOI10_saveit) C++14
100 / 100
 136 ms 11040 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
const int N = 1e3 + 7;
 
vector <int> no, ba;
vector <int> adj[N];
int dis[36][N], bio[N];
 
void dfs(int x) {
	bio[x] = 1;
	no.pb(x);
	for (int y : adj[x]) if (!bio[y]) {
		dfs(y);
		no.pb(-1);
	}
}
 
void encode(int n, int h, int m, int *u, int *v){
	for (int i = 0; i < m; i++) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	memset(dis, -1, sizeof dis);
	for (int i = 0; i < h; i++) {
		queue <int> q;
		q.push(i);
		dis[i][i] = 0;
		while (!q.empty()) {
			int x = q.front(); q.pop();
			for (int y : adj[x]) if (dis[i][y] == -1) {
				dis[i][y] = dis[i][x] + 1;
				q.push(y);
			}
		}
	}
	dfs(0);
	vector <int> en, cur; cur.pb(0);
	for (int i = 1; i < 2*n-1; i++) {
		if (no[i] == -1) {
			en.pb(1);
			cur.pop_back();
		}
		else {
			en.pb(0);
			int x = cur.back();
			cur.pb(no[i]);
			for (int j = 0; j < 10; j++) en.pb((no[i] >> j) & 1);
			ll la = 0;
			for (int j = 0; j < h; j++) la = 3*la+1+dis[j][no[i]]-dis[j][x];
			for (int j = 0; j < 58; j++) en.pb((la >> j) & 1);
		}
	}
	for (int x : en) encode_bit(x);
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e3 + 7;

int res[36][N];
 
void decode(int n, int h) {
	vector <int> cd(h, 0);
	vector <vector <int> > ch;
	for (int i = 0; i < 2*n-2; i++) {
		int o = decode_bit();
		if (o) {
			for (int j = 0; j < h; j++) cd[j] -= ch[ch.size()-1][j];
			ch.pop_back();
		}
		else {
			int x = 0;
			for (int j = 0; j < 10; j++) x += decode_bit() << j;
			ll d = 0;
			for (int j = 0; j < 58; j++) d += (ll)decode_bit() << j;
			vector <int> tmp(h);
			for (int j = h-1; j >= 0; j--) {
				tmp[j] = d%3-1;
				cd[j] += tmp[j];
				d /= 3;
			}
			ch.pb(tmp);
			for (int j = 0; j < h; j++) res[j][x] = cd[j];
		}
	}
	vector <int> ud(h);
	for (int i = 0; i < h; i++) ud[i] = res[i][i];
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < n; j++) {
			hops(i, j, res[i][j]-ud[i]);
		}
	}
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 11040 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
3 Correct 18 ms 6304 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 1 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
5 Correct 18 ms 6344 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 19 ms 6564 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 27 ms 7020 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 14 ms 6292 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 14 ms 6296 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 16 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 16 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 6276 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 31 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 19 ms 6428 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 23 ms 6552 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 43 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 28 ms 7048 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 39 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 24 ms 7052 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 41 ms 7472 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 45 ms 7464 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 37 ms 6936 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 56 ms 7592 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 11040 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
3 Correct 18 ms 6304 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 1 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
5 Correct 18 ms 6344 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 19 ms 6564 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 27 ms 7020 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 14 ms 6292 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 14 ms 6296 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 16 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 16 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 6276 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 31 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 19 ms 6428 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 23 ms 6552 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 43 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 28 ms 7048 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 39 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 24 ms 7052 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 41 ms 7472 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 45 ms 7464 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 37 ms 6936 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 56 ms 7592 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 11040 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
3 Correct 18 ms 6304 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 1 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
5 Correct 18 ms 6344 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 19 ms 6564 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 27 ms 7020 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 14 ms 6292 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 14 ms 6296 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 16 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 16 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 6276 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 31 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 19 ms 6428 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 23 ms 6552 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 43 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 28 ms 7048 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 39 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 24 ms 7052 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 41 ms 7472 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 45 ms 7464 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 37 ms 6936 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 56 ms 7592 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 11040 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 2 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
3 Correct 18 ms 6304 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 1 ms 4880 KB Output is correct - 280 call(s) of encode_bit()
5 Correct 18 ms 6344 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 19 ms 6564 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 27 ms 7020 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 14 ms 6292 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 14 ms 6296 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 16 ms 6304 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 16 ms 6292 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 20 ms 6276 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 31 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 19 ms 6428 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 23 ms 6552 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 43 ms 6876 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 28 ms 7048 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 39 ms 7292 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 24 ms 7052 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 41 ms 7472 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 45 ms 7464 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 37 ms 6936 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 56 ms 7592 KB Output is correct - 69930 call(s) of encode_bit()