oj.uz

Submission #595992

# Submission time Handle Problem Language Result Execution time Memory
595992 2022-07-14T08:47:14 Z Jarif_Rahman Saveit (IOI10_saveit) C++17
50 / 100
 321 ms 10452 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;
    vector<int> p;
    vector<int> diff;

    void dfs(int nd, int d, int H){
        d+=diff[nd];
        hops(H, nd, d);
        for(int x: v[nd]) dfs(x, d, H);
    }
}

void decode(int n, int h){
    v.assign(n, {});
    p.assign(n, -1);

    for(int i = 1; i < n; i++){
        p[i] = bin_to_dec(10);
        v[p[i]].pb(i);
    }

    for(int i = 0; i < h; i++){
        int D = bin_to_dec(10);

        diff.assign(n, 0);
        for(int j = 1; j < n; j++){
            int c = bin_to_dec(2);
            if(c == 1) diff[j] = 1;
            else if(c == 2) diff[j] = -1;
            else diff[j] = 0;
        }

        dfs(0, D, i);
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 10452 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5336 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 31 ms 5692 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 28 ms 5688 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 41 ms 5972 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 36 ms 5496 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 40 ms 5424 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 28 ms 5696 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 37 ms 5516 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 44 ms 6168 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 27 ms 5460 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 24 ms 5768 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 54 ms 6164 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 37 ms 6088 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 47 ms 6336 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 34 ms 5844 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 59 ms 6556 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 69 ms 6700 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 41 ms 6252 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 68 ms 6888 KB Output is partially correct - 82278 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 10452 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5336 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 31 ms 5692 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 28 ms 5688 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 41 ms 5972 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 36 ms 5496 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 40 ms 5424 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 28 ms 5696 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 37 ms 5516 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 44 ms 6168 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 27 ms 5460 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 24 ms 5768 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 54 ms 6164 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 37 ms 6088 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 47 ms 6336 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 34 ms 5844 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 59 ms 6556 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 69 ms 6700 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 41 ms 6252 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 68 ms 6888 KB Output is partially correct - 82278 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 10452 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5336 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 31 ms 5692 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 28 ms 5688 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 41 ms 5972 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 36 ms 5496 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 40 ms 5424 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 28 ms 5696 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 37 ms 5516 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 44 ms 6168 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 27 ms 5460 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 24 ms 5768 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 54 ms 6164 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 37 ms 6088 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 47 ms 6336 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 34 ms 5844 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 59 ms 6556 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 69 ms 6700 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 41 ms 6252 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 68 ms 6888 KB Output is partially correct - 82278 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 10452 KB Output is partially correct - 82278 call(s) of encode_bit()
2 Correct 3 ms 4472 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5336 KB Output is partially correct - 74078 call(s) of encode_bit()
4 Correct 2 ms 4604 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 31 ms 5692 KB Output is partially correct - 74078 call(s) of encode_bit()
6 Correct 28 ms 5688 KB Output is partially correct - 82278 call(s) of encode_bit()
7 Correct 41 ms 5972 KB Output is partially correct - 82278 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is partially correct - 79080 call(s) of encode_bit()
9 Correct 36 ms 5496 KB Output is partially correct - 82278 call(s) of encode_bit()
10 Correct 40 ms 5424 KB Output is partially correct - 82278 call(s) of encode_bit()
11 Correct 28 ms 5696 KB Output is partially correct - 82278 call(s) of encode_bit()
12 Correct 37 ms 5516 KB Output is partially correct - 82278 call(s) of encode_bit()
13 Correct 44 ms 6168 KB Output is partially correct - 82278 call(s) of encode_bit()
14 Correct 27 ms 5460 KB Output is partially correct - 82278 call(s) of encode_bit()
15 Correct 24 ms 5768 KB Output is partially correct - 82278 call(s) of encode_bit()
16 Correct 54 ms 6164 KB Output is partially correct - 82278 call(s) of encode_bit()
17 Correct 37 ms 6088 KB Output is partially correct - 82278 call(s) of encode_bit()
18 Correct 47 ms 6336 KB Output is partially correct - 82278 call(s) of encode_bit()
19 Correct 34 ms 5844 KB Output is partially correct - 82278 call(s) of encode_bit()
20 Correct 59 ms 6556 KB Output is partially correct - 82278 call(s) of encode_bit()
21 Correct 69 ms 6700 KB Output is partially correct - 82278 call(s) of encode_bit()
22 Correct 41 ms 6252 KB Output is partially correct - 82278 call(s) of encode_bit()
23 Correct 68 ms 6888 KB Output is partially correct - 82278 call(s) of encode_bit()