oj.uz

Submission #371242

# Submission time Handle Problem Language Result Execution time Memory
371242 2021-02-26T09:18:48 Z Sorting Saveit (IOI10_saveit) C++17
75 / 100
 255 ms 10616 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;
const int INF = 1e9;

static vector<int> adj[N];
static int n, h, m, par[N], d[N];
static bool vis[N];

void encode_num(int x){
    for(int i = 9; i >= 0; --i)
        encode_bit((x >> i) & 1);
}

void encode_diff(int diff){
    if(diff == -1){
        encode_bit(0);
        encode_bit(0);
    }
    else if(!diff){
        encode_bit(0);
        encode_bit(1);
    }
    else{
        encode_bit(1);
        encode_bit(0);
    }
}

void bfs_0(int u, int p = -1){
    queue<int> q;
    q.push(u);
    vis[u] = true;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(!vis[to]){
                vis[to] = true;
                q.push(to);
                par[to] = v;
            }
    }
}

void bfs(int u){
    fill(d, d + n, INF);

    queue<int> q;
    q.push(u);
    d[u] = 0;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(d[to] == INF){
                d[to] = d[v] + 1;
                q.push(to);
            }
    }

    /*cout << "d: ";
    for(int i = 0; i < n; ++i)
        cout << d[i] << " ";
    cout << endl;

    cout << "par: ";
    for(int i = 1; i < n; ++i)
        cout << par[i] << " ";
    cout << endl;*/

    for(int i = 1; i < n; ++i){
        encode_diff(d[i] - d[par[i]]);
    }
}

void encode(int _nv, int _nh, int _ne, int *v1, int *v2){
    n = _nv, h =_nh, m = _ne;
    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 0; i < m; ++i){
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }

    fill(vis, vis + n, false);
    bfs_0(0);
    for(int i = 1; i < n; ++i)
        encode_num(par[i]);

    for(int i = 1; i < h; ++i)
        bfs(i);
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;

static int n, h, par[N], d[N];
static vector<int> adj[N];
static bool vis[N];

int decode_diff(){
    int bit1 = decode_bit();
    int bit2 = decode_bit();
    if(bit1) return 1;
    if(bit2) return 0;
    return -1;
}

int decode_num(){
    int num = 0;
    for(int i = 9; i >= 0; --i)
        if(decode_bit())
            num += (1 << i);
    return num;
}

void dfs(int u){
    hops(0, u, d[u]);
    for(int to: adj[u]){
        if(to == par[u]) continue;
        d[to] = d[u] + 1;
        dfs(to);
    }
}

void dfs2(int hub, int u, int ans){
    hops(hub, u, ans);
    vis[u] = true;
    for(int to: adj[u])
        if(!vis[to]){
            if(to == par[u]) dfs2(hub, to, ans - d[u]);
            else dfs2(hub, to, ans + d[to]);
        }
}

void decode(int _nv, int _nh) {
    n = _nv, h = _nh;
    if(n == 1){
        hops(0, 0, 0);
        return;
    }

    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 1; i < n; ++i){
        par[i] = decode_num();
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }
    d[0] = 0;
    dfs(0);

    for(int i = 1; i < h; ++i){
        for(int j = 1; j < n; ++j)
            d[j] = decode_diff();
        fill(vis, vis + n, false);
        dfs2(i, i, 0);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 10616 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4748 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 4 ms 4740 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 31 ms 5728 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 34 ms 5856 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 59 ms 6104 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 28 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 32 ms 5620 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 32 ms 5600 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 34 ms 5772 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 30 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 63 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 35 ms 5628 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 33 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 54 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 58 ms 6112 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 74 ms 6368 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 41 ms 5984 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 85 ms 6872 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 81 ms 6748 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 69 ms 6496 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 105 ms 6880 KB Output is partially correct - 79920 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 10616 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4748 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 4 ms 4740 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 31 ms 5728 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 34 ms 5856 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 59 ms 6104 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 28 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 32 ms 5620 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 32 ms 5600 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 34 ms 5772 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 30 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 63 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 35 ms 5628 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 33 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 54 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 58 ms 6112 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 74 ms 6368 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 41 ms 5984 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 85 ms 6872 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 81 ms 6748 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 69 ms 6496 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 105 ms 6880 KB Output is partially correct - 79920 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 10616 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4748 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 4 ms 4740 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 31 ms 5728 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 34 ms 5856 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 59 ms 6104 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 28 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 32 ms 5620 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 32 ms 5600 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 34 ms 5772 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 30 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 63 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 35 ms 5628 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 33 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 54 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 58 ms 6112 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 74 ms 6368 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 41 ms 5984 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 85 ms 6872 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 81 ms 6748 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 69 ms 6496 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 105 ms 6880 KB Output is partially correct - 79920 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 10616 KB Output is partially correct - 79920 call(s) of encode_bit()
2 Correct 3 ms 4748 KB Output is correct - 56 call(s) of encode_bit()
3 Correct 28 ms 5600 KB Output is partially correct - 71920 call(s) of encode_bit()
4 Correct 4 ms 4740 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 31 ms 5728 KB Output is partially correct - 71920 call(s) of encode_bit()
6 Correct 34 ms 5856 KB Output is partially correct - 79920 call(s) of encode_bit()
7 Correct 59 ms 6104 KB Output is partially correct - 79920 call(s) of encode_bit()
8 Correct 28 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 32 ms 5620 KB Output is partially correct - 79920 call(s) of encode_bit()
10 Correct 32 ms 5600 KB Output is partially correct - 79920 call(s) of encode_bit()
11 Correct 34 ms 5772 KB Output is partially correct - 79920 call(s) of encode_bit()
12 Correct 30 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
13 Correct 63 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
14 Correct 35 ms 5628 KB Output is partially correct - 79920 call(s) of encode_bit()
15 Correct 33 ms 5728 KB Output is partially correct - 79920 call(s) of encode_bit()
16 Correct 54 ms 6264 KB Output is partially correct - 79920 call(s) of encode_bit()
17 Correct 58 ms 6112 KB Output is partially correct - 79920 call(s) of encode_bit()
18 Correct 74 ms 6368 KB Output is partially correct - 79920 call(s) of encode_bit()
19 Correct 41 ms 5984 KB Output is partially correct - 79920 call(s) of encode_bit()
20 Correct 85 ms 6872 KB Output is partially correct - 79920 call(s) of encode_bit()
21 Correct 81 ms 6748 KB Output is partially correct - 79920 call(s) of encode_bit()
22 Correct 69 ms 6496 KB Output is partially correct - 79920 call(s) of encode_bit()
23 Correct 105 ms 6880 KB Output is partially correct - 79920 call(s) of encode_bit()