oj.uz

Submission #596043

# Submission time Handle Problem Language Result Execution time Memory
596043 2022-07-14T09:29:54 Z Jarif_Rahman Saveit (IOI10_saveit) C++17
100 / 100
 315 ms 10192 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, int L){
        for(int i = 0; i < L; i++){
            encode_bit(x%2);
            x/=2;
        }
    }

    int ter_to_dec(vector<int> s){
        int rt = 0, p = 1;
        for(int i = 0; i < s.size(); i++) rt+=p*s[i], p*=3;
        return rt;
    }

    void ter_to_bin(vector<int> s){
        dec_to_bin(ter_to_dec(s), 8);
    }

    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], 10);

    for(int i = 0; i < h; i++){
        auto dis = bfs(i);
        dec_to_bin(dis[0], 10);
        vector<int> s;
        for(int j = 1; j < n; j++){
            if(dis[j] == dis[p[j]]) s.pb(0);
            else if(dis[j] == dis[p[j]]+1) s.pb(1);
            else s.pb(2);
            if(s.size() == 5) ter_to_bin(s), s.clear();
        }
        if(!s.empty()) ter_to_bin(s);
    }
}

#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<int> bin_to_ter(){
        int x = bin_to_dec(8);
        vector<int> rt;
        for(int i = 0; i < 5; i++) rt.pb(x%3), x/=3;
        return rt;
    }

    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);
        vector<int> s;
        for(int j = 1; j < n; j++){
            if(s.empty()){
                s = bin_to_ter();
                reverse(s.begin(), s.end());
            }
            if(s.back() == 1) diff[j] = 1;
            else if(s.back() == 2) diff[j] = -1;
            else diff[j] = 0;

            s.pop_back();
        }

        dfs(0, D, i);
    }
}

Compilation message

encoder.cpp: In function 'int {anonymous}::ter_to_dec(std::vector<int>)':
encoder.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0; i < s.size(); i++) rt+=p*s[i], p*=3;
      |                        ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 10192 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5524 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 3 ms 4536 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 26 ms 5476 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 25 ms 5736 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 48 ms 5948 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5436 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 27 ms 5520 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 29 ms 5468 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 25 ms 5664 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 23 ms 5488 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 59 ms 6116 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 24 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 25 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 50 ms 5872 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 36 ms 6016 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 63 ms 6300 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 32 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 78 ms 6492 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 62 ms 6536 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 47 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 69 ms 6808 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 10192 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5524 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 3 ms 4536 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 26 ms 5476 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 25 ms 5736 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 48 ms 5948 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5436 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 27 ms 5520 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 29 ms 5468 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 25 ms 5664 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 23 ms 5488 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 59 ms 6116 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 24 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 25 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 50 ms 5872 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 36 ms 6016 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 63 ms 6300 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 32 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 78 ms 6492 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 62 ms 6536 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 47 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 69 ms 6808 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 10192 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5524 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 3 ms 4536 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 26 ms 5476 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 25 ms 5736 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 48 ms 5948 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5436 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 27 ms 5520 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 29 ms 5468 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 25 ms 5664 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 23 ms 5488 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 59 ms 6116 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 24 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 25 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 50 ms 5872 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 36 ms 6016 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 63 ms 6300 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 32 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 78 ms 6492 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 62 ms 6536 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 47 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 69 ms 6808 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 10192 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5524 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 3 ms 4536 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 26 ms 5476 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 25 ms 5736 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 48 ms 5948 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5436 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 27 ms 5520 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 29 ms 5468 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 25 ms 5664 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 23 ms 5488 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 59 ms 6116 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 24 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 25 ms 5492 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 50 ms 5872 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 36 ms 6016 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 63 ms 6300 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 32 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 78 ms 6492 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 62 ms 6536 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 47 ms 6096 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 69 ms 6808 KB Output is correct - 67950 call(s) of encode_bit()