oj.uz

Submission #1016378

# Submission time Handle Problem Language Result Execution time Memory
1016378 2024-07-08T02:31:04 Z 79brue Saveit (IOI10_saveit) C++17
100 / 100
 136 ms 16804 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    int n, h, m;
    vector<int> link[1002];
    int par[1002];
    bool visited[1002];
    int dist[50][1002];
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n = nv, h = nh, m = ne;
    for(int i=0; i<m; i++){
        link[v1[i]].push_back(v2[i]);
        link[v2[i]].push_back(v1[i]);
    }

    /// BFS 트리를 인코딩
    queue<int> que;
    que.push(0), visited[0] = 1;
    while(!que.empty()){
        int x = que.front(); que.pop();
        for(int y: link[x]){
            if(visited[y]) continue;
            visited[y] = 1, par[y] = x;
            que.push(y);
        }
    }
    for(int i=1; i<n; i++) for(int j=0; j<10; j++) encode_bit((par[i]>>j)&1);

    /// 거리 차이를 인코딩
    for(int s=0; s<h; s++){
        fill(visited, visited+n+1, 0);
        que.push(s), visited[s] = 1, dist[s][s] = 0;
        while(!que.empty()){
            int x = que.front(); que.pop();
            for(int y: link[x]){
                if(visited[y]) continue;
                visited[y] = 1, dist[s][y] = dist[s][x] + 1;
                que.push(y);
            }
        }
        /// dist[s][0] 인코딩
        for(int i=0; i<10; i++) encode_bit((dist[s][0]>>i)&1);
        /// 나머지 거리 인코딩
        vector<int> vec;
        for(int i=1; i<n; i++){
            int v = dist[s][i] - dist[s][par[i]] + 1;
            vec.push_back(v);
            if((int)vec.size() == 5){
                int val = vec[0] + vec[1]*3 + vec[2]*9 + vec[3]*27 + vec[4]*81;
                for(int d=0; d<8; d++) encode_bit((val>>d)&1);
                vec.clear();
            }
        }
        if(!vec.empty()){
            vec.resize(5);
            int val = vec[0] + vec[1]*3 + vec[2]*9 + vec[3]*27 + vec[4]*81;
            for(int d=0; d<8; d++) encode_bit((val>>d)&1);
            vec.clear();
        }
    }
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    int n, h;
    vector<int> link[1002];
    int par[1002];
    int offset[50][1002];
    int dist[50][1002];

    void dfs(int x){
        for(int y: link[x]){
            for(int s=0; s<h; s++) dist[s][y] = dist[s][x] + offset[s][y];
            dfs(y);
        }
    }
}

void decode(int nv, int nh){
    n = nv, h = nh;
    for(int i=1; i<n; i++){
        int v = 0;
        for(int d=0; d<10; d++) v += decode_bit() << d;
        par[i] = v;
        link[v].push_back(i);
    }
    for(int s=0; s<h; s++){
        for(int d=0; d<10; d++) dist[s][0] += decode_bit() << d;
        for(int l=1; l<n; l+=5){
            int v = 0;
            for(int d=0; d<8; d++) v += decode_bit() << d;
            for(int x=l; x<l+5 && x<n; x++){
                offset[s][x] = v % 3 - 1;
                v /= 3;
            }
        }
    }
    dfs(0);
    for(int s=0; s<h; s++){
        for(int i=0; i<n; i++){
            hops(s, i, dist[s][i]);
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16804 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4624 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5640 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 2 ms 4624 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 14 ms 7728 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 7944 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 26 ms 8184 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 14 ms 5904 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 15 ms 7940 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 18 ms 6160 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 18 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 22 ms 11956 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 34 ms 12192 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 17 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 14 ms 11776 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 34 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 24 ms 12024 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 38 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 20 ms 12016 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 37 ms 14672 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 47 ms 14532 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 31 ms 12220 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 54 ms 14680 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16804 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4624 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5640 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 2 ms 4624 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 14 ms 7728 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 7944 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 26 ms 8184 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 14 ms 5904 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 15 ms 7940 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 18 ms 6160 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 18 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 22 ms 11956 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 34 ms 12192 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 17 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 14 ms 11776 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 34 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 24 ms 12024 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 38 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 20 ms 12016 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 37 ms 14672 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 47 ms 14532 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 31 ms 12220 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 54 ms 14680 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16804 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4624 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5640 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 2 ms 4624 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 14 ms 7728 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 7944 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 26 ms 8184 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 14 ms 5904 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 15 ms 7940 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 18 ms 6160 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 18 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 22 ms 11956 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 34 ms 12192 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 17 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 14 ms 11776 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 34 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 24 ms 12024 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 38 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 20 ms 12016 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 37 ms 14672 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 47 ms 14532 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 31 ms 12220 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 54 ms 14680 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 16804 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 1 ms 4624 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 23 ms 5640 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 2 ms 4624 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 14 ms 7728 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 20 ms 7944 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 26 ms 8184 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 14 ms 5904 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 15 ms 7940 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 18 ms 6160 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 18 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 22 ms 11956 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 34 ms 12192 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 17 ms 11780 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 14 ms 11776 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 34 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 24 ms 12024 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 38 ms 12204 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 20 ms 12016 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 37 ms 14672 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 47 ms 14532 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 31 ms 12220 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 54 ms 14680 KB Output is correct - 67950 call(s) of encode_bit()