oj.uz

Submission #595459

# Submission time Handle Problem Language Result Execution time Memory
595459 2022-07-13T18:42:03 Z Jarif_Rahman Saveit (IOI10_saveit) C++17
0 / 100
 212 ms 10352 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    void dec_to_bin(int x){
        for(int i = 0; i < 10; i++){
            encode_bit(x%2);
            x/=2;
        }
    }

    int n;
    vector<vector<int>> v;
    vector<bool> bl;
    vector<int> p;

    void dfs(int nd, int ss){
        if(bl[nd]) return;
        bl[nd] = 1;
        for(int x: v[nd]) if(x != ss) dfs(x, nd);
        p[nd] = ss;
    }

    vector<int> bfs(int s){
        vector<int> dis(n, -1);
        queue<int> Q;

        dis[s] = 0;
        Q.push(s);

        while(!Q.empty()){
            int nd = Q.front(); Q.pop();
            for(int x: v[nd]) if(dis[x] == -1){
                dis[x] = dis[nd]+1;
                Q.push(x);
            }
        }

        return dis;
    }
}

void encode(int _n, int h, int m, int *A, int *B){
    n = _n;
    v.assign(n, {});
    bl.assign(n, 0);
    p.assign(n, -1);

    for(int i = 0; i < m; i++){
        v[A[i]].pb(B[i]);
        v[B[i]].pb(A[i]);
    }

    dfs(0, -1);

    for(int i = 1; i < n; i++) dec_to_bin(p[i]);

    for(int i = 0; i < h; i++){
        auto dis = bfs(i);
        dec_to_bin(dis[0]);
        for(int j = 1; j < n; j++){
            if(dis[j] == dis[p[j]]) encode_bit(0), encode_bit(0);
            else if(dis[j] == dis[p[j]]+1) encode_bit(1), encode_bit(0);
            else encode_bit(0), encode_bit(1);
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    int bin_to_dec(int L){
        int x = 0;
        for(int i = 0; i < L; i++) x+=decode_bit()*(1<<i);
        return x;
    }

    vector<vector<int>> v;
}

void dfs(int nd, int d, int H){
    if(d == -1){
        d = bin_to_dec(10);
    }
    else{
        int c = bin_to_dec(2);
        if(c == 1) d++;
        else if(c == 2) d--;
    }
    hops(H, nd, d);
    for(int x: v[nd]) dfs(x, d, H);
}

void decode(int n, int h){
    v.assign(n, {});
    for(int i = 1; i < n; i++)
        v[bin_to_dec(10)].pb(i);

    for(int i = 0; i < h; i++) dfs(0, -1, i);
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10352 KB wrong parameter
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 27 ms 5500 KB wrong parameter
4 Correct 2 ms 4600 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 28 ms 5608 KB wrong parameter
6 Incorrect 24 ms 5764 KB wrong parameter
7 Incorrect 53 ms 5916 KB wrong parameter
8 Incorrect 19 ms 5500 KB wrong parameter
9 Incorrect 24 ms 5576 KB Output isn't correct
10 Incorrect 26 ms 5516 KB Output isn't correct
11 Incorrect 28 ms 5648 KB Output isn't correct
12 Incorrect 27 ms 5540 KB Output isn't correct
13 Incorrect 57 ms 6132 KB wrong parameter
14 Incorrect 20 ms 5536 KB wrong parameter
15 Incorrect 27 ms 5692 KB Output isn't correct
16 Incorrect 47 ms 6120 KB wrong parameter
17 Incorrect 55 ms 5980 KB wrong parameter
18 Incorrect 61 ms 6244 KB wrong parameter
19 Incorrect 37 ms 5820 KB wrong parameter
20 Incorrect 79 ms 6620 KB Output isn't correct
21 Incorrect 66 ms 6668 KB wrong parameter
22 Incorrect 57 ms 6192 KB wrong parameter
23 Incorrect 64 ms 6896 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10352 KB wrong parameter
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 27 ms 5500 KB wrong parameter
4 Correct 2 ms 4600 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 28 ms 5608 KB wrong parameter
6 Incorrect 24 ms 5764 KB wrong parameter
7 Incorrect 53 ms 5916 KB wrong parameter
8 Incorrect 19 ms 5500 KB wrong parameter
9 Incorrect 24 ms 5576 KB Output isn't correct
10 Incorrect 26 ms 5516 KB Output isn't correct
11 Incorrect 28 ms 5648 KB Output isn't correct
12 Incorrect 27 ms 5540 KB Output isn't correct
13 Incorrect 57 ms 6132 KB wrong parameter
14 Incorrect 20 ms 5536 KB wrong parameter
15 Incorrect 27 ms 5692 KB Output isn't correct
16 Incorrect 47 ms 6120 KB wrong parameter
17 Incorrect 55 ms 5980 KB wrong parameter
18 Incorrect 61 ms 6244 KB wrong parameter
19 Incorrect 37 ms 5820 KB wrong parameter
20 Incorrect 79 ms 6620 KB Output isn't correct
21 Incorrect 66 ms 6668 KB wrong parameter
22 Incorrect 57 ms 6192 KB wrong parameter
23 Incorrect 64 ms 6896 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10352 KB wrong parameter
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 27 ms 5500 KB wrong parameter
4 Correct 2 ms 4600 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 28 ms 5608 KB wrong parameter
6 Incorrect 24 ms 5764 KB wrong parameter
7 Incorrect 53 ms 5916 KB wrong parameter
8 Incorrect 19 ms 5500 KB wrong parameter
9 Incorrect 24 ms 5576 KB Output isn't correct
10 Incorrect 26 ms 5516 KB Output isn't correct
11 Incorrect 28 ms 5648 KB Output isn't correct
12 Incorrect 27 ms 5540 KB Output isn't correct
13 Incorrect 57 ms 6132 KB wrong parameter
14 Incorrect 20 ms 5536 KB wrong parameter
15 Incorrect 27 ms 5692 KB Output isn't correct
16 Incorrect 47 ms 6120 KB wrong parameter
17 Incorrect 55 ms 5980 KB wrong parameter
18 Incorrect 61 ms 6244 KB wrong parameter
19 Incorrect 37 ms 5820 KB wrong parameter
20 Incorrect 79 ms 6620 KB Output isn't correct
21 Incorrect 66 ms 6668 KB wrong parameter
22 Incorrect 57 ms 6192 KB wrong parameter
23 Incorrect 64 ms 6896 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 10352 KB wrong parameter
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 27 ms 5500 KB wrong parameter
4 Correct 2 ms 4600 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 28 ms 5608 KB wrong parameter
6 Incorrect 24 ms 5764 KB wrong parameter
7 Incorrect 53 ms 5916 KB wrong parameter
8 Incorrect 19 ms 5500 KB wrong parameter
9 Incorrect 24 ms 5576 KB Output isn't correct
10 Incorrect 26 ms 5516 KB Output isn't correct
11 Incorrect 28 ms 5648 KB Output isn't correct
12 Incorrect 27 ms 5540 KB Output isn't correct
13 Incorrect 57 ms 6132 KB wrong parameter
14 Incorrect 20 ms 5536 KB wrong parameter
15 Incorrect 27 ms 5692 KB Output isn't correct
16 Incorrect 47 ms 6120 KB wrong parameter
17 Incorrect 55 ms 5980 KB wrong parameter
18 Incorrect 61 ms 6244 KB wrong parameter
19 Incorrect 37 ms 5820 KB wrong parameter
20 Incorrect 79 ms 6620 KB Output isn't correct
21 Incorrect 66 ms 6668 KB wrong parameter
22 Incorrect 57 ms 6192 KB wrong parameter
23 Incorrect 64 ms 6896 KB wrong parameter