oj.uz

Submission #287078

# Submission time Handle Problem Language Result Execution time Memory
287078 2020-08-31T11:30:26 Z Kastanda Saveit (IOI10_saveit) C++11
100 / 100
 241 ms 11552 KB 
// M
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
static const int N = 1009;
static int n, k, m, M[N], P[N], D[N];
static vector < int > Adj[N];

void DFS(int v)
{
        M[v] = 1;
        for (int u : Adj[v])
                if (!M[u])
                        P[u] = v, DFS(u);
}

void encode(int nv, int nh, int ne, int *v1, int *v2)
{
        n = nv; k = nh; m = ne;
        for (int i = 0; i < m; i ++)
                Adj[v1[i]].push_back(v2[i]), Adj[v2[i]].push_back(v1[i]);
        DFS(0);

        for (int i = 1; i < n; i ++)
                for (int j = 0; j < 10; j ++)
                        encode_bit((P[i] >> j) & 1);

        int C = 5;
        int RQB = 8;

        for (int h = 0; h < k; h ++)
        {
                queue < int > qu;
                memset(D, -1, sizeof(D));
                D[h] = 0; qu.push(h);
                while (qu.size())
                {
                        int v = qu.front();
                        qu.pop();
                        for (int u : Adj[v])
                                if (D[u] == -1)
                                        D[u] = D[v] + 1, qu.push(u);
                }
                for (int i = 0; i < n; i += C)
                {
                        int val = 0;
                        for (int j = i; j < min(i + C, n); j ++)
                        {
                                int r = 0;
                                if (D[P[j]] == D[j])
                                        r = 1;
                                if (D[P[j]] > D[j])
                                        r = 2;
                                val = val * 3 + r;
                        }

                        for (int j = 0; j < RQB; j ++)
                                encode_bit((val >> j) & 1);
                }
        }
        return ;
}
// M
#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
static const int N = 1009;
static int n, k, P[N], D[N], F[N];
static vector < int > Ch[N];

void decode(int nv, int nh)
{
        n = nv; k = nh;

        for (int i = 1; i < n; i ++)
        {
                for (int j = 0; j < 10; j ++)
                        P[i] |= ((int)decode_bit()) << j;
                Ch[P[i]].push_back(i);
        }

        int C = 5;
        int RQB = 8;

        for (int h = 0; h < k; h ++)
        {
                for (int i = 0; i < n; i += C)
                {
                        int val = 0;
                        for (int j = 0; j < RQB; j ++)
                                val |= ((int)decode_bit()) << j;
                        for (int j = min(i + C, n) - 1; j >= i; j --)
                                F[j] = val % 3, val /= 3;
                }

                memset(D, -1, sizeof(D));
                queue < int > qu;
                qu.push(h); D[h] = 0;
                while (qu.size())
                {
                        int v = qu.front();
                        qu.pop();
                        if (v > 0 && D[P[v]] == -1)
                        {
                                D[P[v]] = D[v] + F[v] - 1;
                                qu.push(P[v]);
                        }
                        for (int u : Ch[v])
                                if (D[u] == -1)
                                {
                                        D[u] = D[v] - F[u] + 1;
                                        qu.push(u);
                                }
                }
                for (int i = 0; i < n; i ++)
                        hops(h, i, D[i]);
        }
        return ;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 11552 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4808 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 36 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4788 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 27 ms 5632 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5648 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 56 ms 6072 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5624 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 38 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 39 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 26 ms 5756 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 72 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5696 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 56 ms 5956 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 66 ms 6392 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 106 ms 5852 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 103 ms 6580 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 84 ms 6716 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 66 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 96 ms 7128 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 11552 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4808 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 36 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4788 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 27 ms 5632 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5648 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 56 ms 6072 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5624 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 38 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 39 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 26 ms 5756 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 72 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5696 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 56 ms 5956 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 66 ms 6392 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 106 ms 5852 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 103 ms 6580 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 84 ms 6716 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 66 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 96 ms 7128 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 11552 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4808 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 36 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4788 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 27 ms 5632 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5648 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 56 ms 6072 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5624 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 38 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 39 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 26 ms 5756 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 72 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5696 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 56 ms 5956 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 66 ms 6392 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 106 ms 5852 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 103 ms 6580 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 84 ms 6716 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 66 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 96 ms 7128 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 11552 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 4 ms 4808 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 36 ms 5504 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 4 ms 4788 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 27 ms 5632 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 41 ms 5648 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 56 ms 6072 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 28 ms 5624 KB Output is correct - 65184 call(s) of encode_bit()
9 Correct 30 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 38 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 39 ms 5656 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 26 ms 5756 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 72 ms 6328 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 28 ms 5696 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 33 ms 5632 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 75 ms 6008 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 56 ms 5956 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 66 ms 6392 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 106 ms 5852 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 103 ms 6580 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 84 ms 6716 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 66 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 96 ms 7128 KB Output is correct - 67590 call(s) of encode_bit()