oj.uz

Submission #252859

# Submission time Handle Problem Language Result Execution time Memory
252859 2020-07-26T11:09:06 Z SamAnd Saveit (IOI10_saveit) C++17
50 / 100
 300 ms 13808 KB 
#include "grader.h"
#include "encoder.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int N = 1002;

int nn, m, u;
vector<int> a[N];
int d[N];
bool c[N];
void bfs(int x)
{
	for (int i = 0; i < nn; ++i)
	{
		c[i] = false;
		d[i] = 0;
	}
	queue<int> q;
	c[x] = true;
	q.push(x);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 0; i < a[x].size(); ++i)
		{
			int h = a[x][i];
			if (!c[h])
			{
				c[h] = true;
				d[h] = d[x] + 1;
				q.push(h);
			}
		}
	}
}
void encode(int nv, int nh, int ne, int *v1, int *v2) {
	nn = nv;
	u = nh;
	m = ne;
	for (int i = 0; i < m; ++i)
	{
		a[v1[i]].push_back(v2[i]);
		a[v2[i]].push_back(v1[i]);
	}
	for (int i = 0; i < u; ++i)
	{
		bfs(i);
		for (int j = 0; j < nn; ++j)
		{
			vector<int> v;
			if (!d[j])
			{
				for (int k = 0; k<9; ++k)
					encode_bit(0);
				encode_bit(0);
				continue;
			}
			while (d[j])
			{
				v.push_back((d[j] % 2));
				d[j] /= 2;
			}
			for (int k = 0; k < (10 - v.size()); ++k)
			{
				encode_bit(0);
			}
			for (int k = v.size() - 1; k >= 0; --k)
			{
				encode_bit(v[k]);
			}
		}
	}
	return;
}

#include "grader.h"
#include "decoder.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
using namespace std;
const int N = 1002;

void decode(int nv, int nh) {
	int v = 0;
	int u = 0;
	int n = 0;
	int i = 0;
	while (1)
	{
		++i;
		n *= 2;
		n += decode_bit();
		if (i % 10 == 0)
		{
			hops(v, u, n);
			++u;
			if (u == nv)
			{
				++v;
				u = 0;
			}
			if (v == nh)
			{
				break;
			}
			n = 0;
		}
	}
}

Compilation message

encoder.cpp: In function 'void bfs(int)':
encoder.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[x].size(); ++i)
                   ~~^~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < (10 - v.size()); ++k)
                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 13808 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4736 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 94 ms 7424 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4812 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 92 ms 7672 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 97 ms 7792 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 112 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 96 ms 7552 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 95 ms 7916 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 96 ms 7912 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 99 ms 8036 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 95 ms 7712 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 120 ms 8708 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 95 ms 7920 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 98 ms 7868 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 8552 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 112 ms 8208 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 121 ms 8560 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 113 ms 8108 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 132 ms 8928 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 136 ms 9068 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 123 ms 8520 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 142 ms 9064 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 13808 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4736 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 94 ms 7424 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4812 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 92 ms 7672 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 97 ms 7792 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 112 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 96 ms 7552 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 95 ms 7916 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 96 ms 7912 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 99 ms 8036 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 95 ms 7712 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 120 ms 8708 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 95 ms 7920 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 98 ms 7868 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 8552 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 112 ms 8208 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 121 ms 8560 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 113 ms 8108 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 132 ms 8928 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 136 ms 9068 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 123 ms 8520 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 142 ms 9064 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 13808 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4736 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 94 ms 7424 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4812 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 92 ms 7672 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 97 ms 7792 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 112 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 96 ms 7552 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 95 ms 7916 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 96 ms 7912 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 99 ms 8036 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 95 ms 7712 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 120 ms 8708 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 95 ms 7920 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 98 ms 7868 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 8552 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 112 ms 8208 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 121 ms 8560 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 113 ms 8108 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 132 ms 8928 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 136 ms 9068 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 123 ms 8520 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 142 ms 9064 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 13808 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4736 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 94 ms 7424 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4812 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 92 ms 7672 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 97 ms 7792 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 112 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 96 ms 7552 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 95 ms 7916 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 96 ms 7912 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 99 ms 8036 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 95 ms 7712 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 120 ms 8708 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 95 ms 7920 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 98 ms 7868 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 115 ms 8552 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 112 ms 8208 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 121 ms 8560 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 113 ms 8108 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 132 ms 8928 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 136 ms 9068 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 123 ms 8520 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 142 ms 9064 KB Output is partially correct - 360000 call(s) of encode_bit()