oj.uz

Submission #763662

# Submission time Handle Problem Language Result Execution time Memory
763662 2023-06-22T15:13:37 Z lukameladze Saveit (IOI10_saveit) C++17
100 / 100
 205 ms 10272 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 1005;
int n,k,m,dist[N][N],par[N];
vector <int> v[N];
void bfs(int x, int ty) {
    for (int i = 0; i < n; i++) {
        dist[x][i] = -1;
    }
    dist[x][x] = 0; queue <int> q; q.push(x);
    while (!q.empty()) {
        int y = q.front();
        q.pop();
        for (int to : v[y]) {
            if (dist[x][to] == -1) {
                if (ty == 1) {
                    par[to] = y; // mst[y].pb(to);
                }
                dist[x][to] = dist[x][y] + 1;
                q.push(to);
            }
        }
    }
}
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++) {
        int a = v1[i], b = v2[i];
        v[a].pb(b); v[b].pb(a);
    }
    for (int i = 0; i < k; i++) {
        bfs(i, 0);
    }
    bfs(0, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 10; j++) { // encode jth bit of par[i]
            if (par[i]&(1<<j)) encode_bit(1);
            else encode_bit(0);
        }
    }
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < 10; j++) {
            if ((1<<j)&dist[i][0]) encode_bit(1);
            else encode_bit(0);
        }
        for (int j = 1; j < n; j+=5) {
            int cur_sum = 0;
            for (int z = j; z < j + 5; z++) {
                int vl = 0;
                if (dist[i][z] == dist[i][par[z]] - 1 || z >= n) vl = 0;
                else if (dist[i][z] == dist[i][par[z]]) vl = 1;
                else if (dist[i][z] == dist[i][par[z]] + 1) vl = 2;
                else assert(false);
                cur_sum = cur_sum * 3 + vl;
            }

            for (int z = 0; z < 8; z++) {
                if ((1<<z)&cur_sum) encode_bit(1);
                else encode_bit(0);
            }
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int MX = 1000 + 5;
int diff[MX];
vector <int> g[MX];
void dfs(int a, int p) {
    if (p != -1) diff[a] += diff[p];
    for (int to : g[a]) {
        if (to == p) continue;
        dfs(to, a);
    }
}

void decode(int nv, int nh) {
    int n = nv, k = nh;
    for (int i = 1; i < n; i++) {
        int cur_par = 0;
        for (int j = 0; j < 10; j++) {
            int x = decode_bit();
            if (x) cur_par += (1<<j);
        }
        g[cur_par].pb(i);
    }
    for (int i = 0; i < k; i++) {
        int cur_val = 0;
        for (int j = 0; j < 10; j++) {
            int x = decode_bit();
            if (x) cur_val += (1<<j);
        }
        diff[0] = cur_val;
        for (int j = 1; j < n; j+=5) {
            int cur_sum = 0;
            for (int z = 0; z < 8; z++) {
                int x = decode_bit();
                if(x == 1) cur_sum += (1<<z);
            }
            for (int ve = j + 4; ve >= j; ve--) {
                if (cur_sum % 3 == 0) diff[ve] = -1;
                else if (cur_sum % 3 == 1) diff[ve] = 0;
                else if (cur_sum % 3 == 2) diff[ve] = 1;
                cur_sum /= 3;
            }
        }
        dfs(0, -1);
        for (int j = 0; j < n; j++) {
            hops(i, j, diff[j]);
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10272 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4608 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 19 ms 5384 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 1 ms 4616 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 25 ms 5560 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 5560 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 31 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 18 ms 5380 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 22 ms 5504 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 22 ms 5600 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 27 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 16 ms 5508 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 47 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 23 ms 5652 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 24 ms 5612 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 46 ms 5996 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 32 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 52 ms 6212 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 37 ms 5636 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 63 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 66 ms 6528 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 34 ms 6256 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 75 ms 6748 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10272 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4608 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 19 ms 5384 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 1 ms 4616 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 25 ms 5560 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 5560 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 31 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 18 ms 5380 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 22 ms 5504 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 22 ms 5600 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 27 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 16 ms 5508 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 47 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 23 ms 5652 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 24 ms 5612 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 46 ms 5996 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 32 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 52 ms 6212 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 37 ms 5636 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 63 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 66 ms 6528 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 34 ms 6256 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 75 ms 6748 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10272 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4608 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 19 ms 5384 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 1 ms 4616 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 25 ms 5560 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 5560 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 31 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 18 ms 5380 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 22 ms 5504 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 22 ms 5600 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 27 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 16 ms 5508 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 47 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 23 ms 5652 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 24 ms 5612 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 46 ms 5996 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 32 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 52 ms 6212 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 37 ms 5636 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 63 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 66 ms 6528 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 34 ms 6256 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 75 ms 6748 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 10272 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4608 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 19 ms 5384 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 1 ms 4616 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 25 ms 5560 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 5560 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 31 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 18 ms 5380 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 22 ms 5504 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 22 ms 5600 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 27 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 16 ms 5508 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 47 ms 5964 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 23 ms 5652 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 24 ms 5612 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 46 ms 5996 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 32 ms 6008 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 52 ms 6212 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 37 ms 5636 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 63 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 66 ms 6528 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 34 ms 6256 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 75 ms 6748 KB Output is correct - 67950 call(s) of encode_bit()