oj.uz

Submission #998139

# Submission time Handle Problem Language Result Execution time Memory
998139 2024-06-13T10:26:03 Z bachhoangxuan Saveit (IOI10_saveit) C++17
100 / 100
 159 ms 16548 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;

void encode(int N, int H, int P, int *A, int *B){
    vector<vector<int>> edge(N);
    vector<int> par(N),dist(N);
    for(int i=0;i<P;i++){
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    for(int i=0;i<H;i++){
        dist.assign(N,-1);
        queue<int> q;q.push(i);dist[i]=0;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int v:edge[u]){
                if(dist[v]!=-1) continue;
                q.push(v);dist[v]=dist[u]+1;
                if(!i) par[v]=u;
            }
        }
        if(!i){
            for(int j=1;j<N;j++) for(int k=0;k<10;k++) encode_bit(par[j]>>k&1);
        }
        for(int j=1;j<N;j+=5){
            int num=0;
            for(int u=j;u<min(N,j+5);u++){
                num=num*3+dist[u]-dist[par[u]]+1;
                //cout << i << ' ' << u << ' ' << dist[u]-dist[par[u]] << '\n';
            }
            for(int k=0;k<8;k++) encode_bit(num>>k&1);
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;

void decode(int N, int H) {
    vector<int> par(N),dist(N);
    vector<vector<int>> edge(N);
    vector<vector<int>> dd(H,vector<int>(N,0));
    for(int i=1;i<N;i++){
        for(int j=0;j<10;j++) par[i]+=decode_bit()<<j;
        edge[par[i]].push_back(i);
        edge[i].push_back(par[i]);
        //cout << par[i] << '\n';
    }
    for(int i=0;i<H;i++){
        //cout << '*' << i << '\n';
        for(int j=1;j<N;j+=5){
            int num=0;
            for(int k=0;k<8;k++) num+=decode_bit()<<k;
            for(int u=min(N,j+5)-1;u>=j;u--){
                dist[u]=num%3-1;num/=3;
                //cout << u << ' ' << par[u] <<  ' ' << dist[u] << '\n';
            }
        }
        function<void(int,int)> dfs = [&](int u,int p){
            for(int v:edge[u]){
                if(v==p) continue;
                int w=(par[v]==u?dist[v]:-dist[u]);
                dd[i][v]=dd[i][u]+w;dfs(v,u);
            }
        };
        dd[i][i]=0;
        dfs(i,-1);
        for(int j=0;j<N;j++){
            //cout << "hh " << i << ' ' << j << ' ' << dd[i][j] << '\n';
            hops(i,j,dd[i][j]);
        }
        //cout << '\n';
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16548 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 11268 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 13 ms 11264 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 1 ms 11260 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 14 ms 11520 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 25 ms 11712 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 12 ms 11268 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 13 ms 11728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 14 ms 11500 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 16 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 14 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 28 ms 11704 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 18 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 17 ms 11764 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 28 ms 12024 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 24 ms 12020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 38 ms 12004 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 20 ms 11516 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 39 ms 14576 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 43 ms 14412 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 36 ms 11688 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 45 ms 14508 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16548 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 11268 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 13 ms 11264 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 1 ms 11260 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 14 ms 11520 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 25 ms 11712 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 12 ms 11268 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 13 ms 11728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 14 ms 11500 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 16 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 14 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 28 ms 11704 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 18 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 17 ms 11764 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 28 ms 12024 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 24 ms 12020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 38 ms 12004 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 20 ms 11516 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 39 ms 14576 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 43 ms 14412 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 36 ms 11688 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 45 ms 14508 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16548 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 11268 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 13 ms 11264 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 1 ms 11260 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 14 ms 11520 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 25 ms 11712 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 12 ms 11268 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 13 ms 11728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 14 ms 11500 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 16 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 14 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 28 ms 11704 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 18 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 17 ms 11764 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 28 ms 12024 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 24 ms 12020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 38 ms 12004 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 20 ms 11516 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 39 ms 14576 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 43 ms 14412 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 36 ms 11688 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 45 ms 14508 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 16548 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 1 ms 11268 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 13 ms 11264 KB Output is correct - 60830 call(s) of encode_bit()
4 Correct 1 ms 11260 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 14 ms 11520 KB Output is correct - 60830 call(s) of encode_bit()
6 Correct 19 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 25 ms 11712 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 12 ms 11268 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 13 ms 11728 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 14 ms 11500 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 16 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 14 ms 11524 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 28 ms 11704 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 18 ms 11644 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 17 ms 11764 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 28 ms 12024 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 24 ms 12020 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 38 ms 12004 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 20 ms 11516 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 39 ms 14576 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 43 ms 14412 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 36 ms 11688 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 45 ms 14508 KB Output is correct - 67590 call(s) of encode_bit()