oj.uz

Submission #371241

# Submission time Handle Problem Language Result Execution time Memory
371241 2021-02-26T09:15:32 Z Sorting Saveit (IOI10_saveit) C++17
0 / 100
 387 ms 11000 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[u] + 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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 11000 KB Output isn't correct
2 Incorrect 3 ms 4748 KB Output isn't correct
3 Incorrect 28 ms 5600 KB Output isn't correct
4 Incorrect 4 ms 4704 KB Output isn't correct
5 Incorrect 30 ms 5968 KB Output isn't correct
6 Incorrect 34 ms 5636 KB Output isn't correct
7 Incorrect 50 ms 6392 KB Output isn't correct
8 Incorrect 33 ms 5472 KB Output isn't correct
9 Incorrect 33 ms 5628 KB Output isn't correct
10 Incorrect 32 ms 5600 KB Output isn't correct
11 Incorrect 35 ms 5728 KB Output isn't correct
12 Incorrect 38 ms 5600 KB Output isn't correct
13 Incorrect 62 ms 6240 KB Output isn't correct
14 Incorrect 32 ms 5600 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 72 ms 6112 KB Output isn't correct
17 Incorrect 59 ms 6112 KB Output isn't correct
18 Incorrect 56 ms 6608 KB Output isn't correct
19 Incorrect 47 ms 5856 KB Output isn't correct
20 Incorrect 76 ms 6872 KB Output isn't correct
21 Incorrect 95 ms 6820 KB Output isn't correct
22 Incorrect 59 ms 6464 KB Output isn't correct
23 Incorrect 92 ms 6880 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 11000 KB Output isn't correct
2 Incorrect 3 ms 4748 KB Output isn't correct
3 Incorrect 28 ms 5600 KB Output isn't correct
4 Incorrect 4 ms 4704 KB Output isn't correct
5 Incorrect 30 ms 5968 KB Output isn't correct
6 Incorrect 34 ms 5636 KB Output isn't correct
7 Incorrect 50 ms 6392 KB Output isn't correct
8 Incorrect 33 ms 5472 KB Output isn't correct
9 Incorrect 33 ms 5628 KB Output isn't correct
10 Incorrect 32 ms 5600 KB Output isn't correct
11 Incorrect 35 ms 5728 KB Output isn't correct
12 Incorrect 38 ms 5600 KB Output isn't correct
13 Incorrect 62 ms 6240 KB Output isn't correct
14 Incorrect 32 ms 5600 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 72 ms 6112 KB Output isn't correct
17 Incorrect 59 ms 6112 KB Output isn't correct
18 Incorrect 56 ms 6608 KB Output isn't correct
19 Incorrect 47 ms 5856 KB Output isn't correct
20 Incorrect 76 ms 6872 KB Output isn't correct
21 Incorrect 95 ms 6820 KB Output isn't correct
22 Incorrect 59 ms 6464 KB Output isn't correct
23 Incorrect 92 ms 6880 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 11000 KB Output isn't correct
2 Incorrect 3 ms 4748 KB Output isn't correct
3 Incorrect 28 ms 5600 KB Output isn't correct
4 Incorrect 4 ms 4704 KB Output isn't correct
5 Incorrect 30 ms 5968 KB Output isn't correct
6 Incorrect 34 ms 5636 KB Output isn't correct
7 Incorrect 50 ms 6392 KB Output isn't correct
8 Incorrect 33 ms 5472 KB Output isn't correct
9 Incorrect 33 ms 5628 KB Output isn't correct
10 Incorrect 32 ms 5600 KB Output isn't correct
11 Incorrect 35 ms 5728 KB Output isn't correct
12 Incorrect 38 ms 5600 KB Output isn't correct
13 Incorrect 62 ms 6240 KB Output isn't correct
14 Incorrect 32 ms 5600 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 72 ms 6112 KB Output isn't correct
17 Incorrect 59 ms 6112 KB Output isn't correct
18 Incorrect 56 ms 6608 KB Output isn't correct
19 Incorrect 47 ms 5856 KB Output isn't correct
20 Incorrect 76 ms 6872 KB Output isn't correct
21 Incorrect 95 ms 6820 KB Output isn't correct
22 Incorrect 59 ms 6464 KB Output isn't correct
23 Incorrect 92 ms 6880 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 11000 KB Output isn't correct
2 Incorrect 3 ms 4748 KB Output isn't correct
3 Incorrect 28 ms 5600 KB Output isn't correct
4 Incorrect 4 ms 4704 KB Output isn't correct
5 Incorrect 30 ms 5968 KB Output isn't correct
6 Incorrect 34 ms 5636 KB Output isn't correct
7 Incorrect 50 ms 6392 KB Output isn't correct
8 Incorrect 33 ms 5472 KB Output isn't correct
9 Incorrect 33 ms 5628 KB Output isn't correct
10 Incorrect 32 ms 5600 KB Output isn't correct
11 Incorrect 35 ms 5728 KB Output isn't correct
12 Incorrect 38 ms 5600 KB Output isn't correct
13 Incorrect 62 ms 6240 KB Output isn't correct
14 Incorrect 32 ms 5600 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 72 ms 6112 KB Output isn't correct
17 Incorrect 59 ms 6112 KB Output isn't correct
18 Incorrect 56 ms 6608 KB Output isn't correct
19 Incorrect 47 ms 5856 KB Output isn't correct
20 Incorrect 76 ms 6872 KB Output isn't correct
21 Incorrect 95 ms 6820 KB Output isn't correct
22 Incorrect 59 ms 6464 KB Output isn't correct
23 Incorrect 92 ms 6880 KB Output isn't correct