oj.uz

Submission #63905

# Submission time Handle Problem Language Result Execution time Memory
63905 2018-08-03T06:44:33 Z YaDon4ick Saveit (IOI10_saveit) C++14
100 / 100
 249 ms 11560 KB 
#include "grader.h"
#include "encoder.h"

//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = 1005;
const int K = 40;

using namespace std;

static int n, d[K][N], parent[N];
static vector < int > g[N];

void bfs(int start)
{
	fill(d[start], d[start] + n, -1);
	d[start][start] = 0;
	queue < int > q;
	q.push(start);
	while(!q.empty())
	{
		int v = q.front();
		q.pop();
		for (auto to : g[v])
		{
			if (d[start][to] == -1)
			{
				d[start][to] = d[start][v] + 1;
				q.push(to);
			}
		}
	}
}

void dfs(int v)
{
	for (auto to : g[v])
	{
		if (parent[to] == -1)
		{
			parent[to] = v;
			dfs(to);
		}	
	}
}

void encodeNum(int x, int len)
{
	for (int i = 0; i < len; i++)
	{
		encode_bit(x & 1);
		x >>= 1;
	}
}

void encode(int _n, int k, int m, int *v1, int *v2)
{
	n = _n;	
	//~read
	for (int i = 0; i < m; i++)
	{
		int v = v1[i], u = v2[i];
		g[v].pb(u), g[u].pb(v);
	}
	//~calc_d
	for (int i = 0; i < k; i++)
		bfs(i);
	//~spanning_tree
	fill(parent, parent + n, -1);
	dfs(0);	
	//~encode_tree
	for (int i = 1; i < n; i++)
		encodeNum(parent[i], 10);
  	//~encode_dist_from_0
  	for (int i = 0; i < k; i++)
  		encodeNum(d[0][i], 10);
	//~encode_res
	for (int v = 0; v < k; v++)
	{	
		for (int j = 0; j < n; j += 5)
		{
			int mask = 0;
			for (int u = min(n - 1, j + 4); u >= j; u--)
			{
				mask *= 3;
				if (d[v][u] == d[v][parent[u]])
					mask++;
				else if (d[v][u] == d[v][parent[u]] + 1)
					mask += 2;				
			}
			encodeNum(mask, 8);
		}	
	}
  	return;
}

#include "grader.h"
#include "decoder.h"

//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = 1005;
const int K = 40;

using namespace std;

vector < int > g[N];
int d[K][N], add[K][N];

int decodeNum(int len)
{
	int res = 0;
	for (int i = 0; i < len; i++)
	{
		int bit = decode_bit();
		res += bit * (1 << i);		
	}
	return res;	
}

void decode(int n, int k) 
{
	//~decode_tree
	for (int v = 1; v < n; v++)
	{
		int u = decodeNum(10);
		g[u].pb(v);
	}
	//~decode_d
	for (int i = 0; i < k; i++)
		d[i][0] = decodeNum(10);
	//~decode_add
	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j < n; j += 5)
		{
			int mask = decodeNum(8);
			for (int u = j; u < j + 5 && u < n; u++)
			{
				add[i][u] = (mask % 3) - 1;
				mask /= 3;
			}			
		}                           	
	}
	//~solve
	for (int i = 0; i < k; i++)
	{
		queue < int > q;
		q.push(0);
		while(!q.empty())
		{
			int v = q.front();
			q.pop();
			for (auto to : g[v])
			{
				d[i][to] = d[i][v] + add[i][to];
				q.push(to);
			}
		}
	}
	//~decode_ans
	for (int i = 0; i < k; i++)
		for (int j = 0; j < n; j++)
			hops(i, j, d[i][j]);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 11560 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4704 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 28 ms 5932 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 30 ms 6120 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 33 ms 6152 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 64 ms 6428 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5932 KB Output is correct - 65544 call(s) of encode_bit()
9 Correct 30 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 31 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 6048 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5984 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 78 ms 6596 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 31 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 31 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 71 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 68 ms 6556 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 86 ms 6720 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 41 ms 6312 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 79 ms 6896 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 109 ms 7084 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 62 ms 6676 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 121 ms 7324 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 11560 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4704 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 28 ms 5932 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 30 ms 6120 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 33 ms 6152 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 64 ms 6428 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5932 KB Output is correct - 65544 call(s) of encode_bit()
9 Correct 30 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 31 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 6048 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5984 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 78 ms 6596 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 31 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 31 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 71 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 68 ms 6556 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 86 ms 6720 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 41 ms 6312 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 79 ms 6896 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 109 ms 7084 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 62 ms 6676 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 121 ms 7324 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 11560 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4704 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 28 ms 5932 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 30 ms 6120 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 33 ms 6152 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 64 ms 6428 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5932 KB Output is correct - 65544 call(s) of encode_bit()
9 Correct 30 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 31 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 6048 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5984 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 78 ms 6596 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 31 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 31 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 71 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 68 ms 6556 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 86 ms 6720 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 41 ms 6312 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 79 ms 6896 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 109 ms 7084 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 62 ms 6676 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 121 ms 7324 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 11560 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4704 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 28 ms 5932 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 30 ms 6120 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 33 ms 6152 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 64 ms 6428 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5932 KB Output is correct - 65544 call(s) of encode_bit()
9 Correct 30 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 31 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 6048 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5984 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 78 ms 6596 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 31 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 31 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 71 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 68 ms 6556 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 86 ms 6720 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 41 ms 6312 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 79 ms 6896 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 109 ms 7084 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 62 ms 6676 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 121 ms 7324 KB Output is correct - 67950 call(s) of encode_bit()