oj.uz

답안 #444339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
444339 2021-07-13T17:13:38 Z JovanB 저장 (Saveit) (IOI10_saveit) C++17
100 / 100
 230 ms 12604 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

static int parent[10000];
static int dist[36][10000];
static int info[36][10000];

static vector <int> graf[10000];

void bfs(int root, int n){
    for(int i=0; i<n; i++) dist[root][i] = n+5;
    dist[root][root] = 0;
    queue <int> q;
    q.push(root);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto c : graf[v]){
            if(dist[root][c] > dist[root][v] + 1){
                dist[root][c] = dist[root][v] + 1;
                q.push(c);
                if(root == 0) parent[c] = v;
            }
        }
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    for(int i=0; i<ne; i++){
        graf[v1[i]].push_back(v2[i]);
        graf[v2[i]].push_back(v1[i]);
    }
    for(int i=0; i<nh; i++) bfs(i, nv);
    for(int i=1; i<nv; i++){
        for(int j=0; j<10; j++){
            if((1 << j) & parent[i]) encode_bit(1);
            else encode_bit(0);
        }
    }
    vector <pair <int, int>> pairs;
    for(int i=0; i<nh; i++){
        for(int j=1; j<nv; j++){
            if(dist[i][j] == dist[i][parent[j]] + 1) info[i][j] = 1;
            else if(dist[i][j] == dist[i][parent[j]] - 1) info[i][j] = 2;
            pairs.push_back({i, j});
        }
    }
    while(pairs.size()%3) pairs.push_back({0, 0});
    for(int i=0; i<pairs.size(); i+=3){
        pair <int, int> a = pairs[i];
        pair <int, int> b = pairs[i+1];
        pair <int, int> c = pairs[i+2];
        int tr = info[c.first][c.second];
        tr = 3*tr + info[b.first][b.second];
        tr = 3*tr + info[a.first][a.second];
        for(int j=0; j<5; j++){
            if((1 << j) & tr) encode_bit(1);
            else encode_bit(0);
        }
    }
}

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

using namespace std;

static int parent[10000];
static int info[36][10000];
static int dist[36][10000];

static vector <int> graf[10000];

void dfs(int v, int p, int k){
    if(p != -1){
        if(info[k][v] == 0) dist[k][v] = dist[k][p];
        else if(info[k][v] == 1) dist[k][v] = dist[k][p] + 1;
        else dist[k][v] = dist[k][p] - 1;
    }
    for(auto c : graf[v]){
        dfs(c, v, k);
    }
}

void decode(int nv, int nh){
    int tr = 0;
    for(int i=1; i<nv; i++){
        for(int j=0; j<10; j++){
            parent[i] += (1 << j)*decode_bit();
        }
        graf[parent[i]].push_back(i);
    }
    vector <pair <int, int>> pairs;
    for(int i=0; i<nh; i++){
        for(int j=1; j<nv; j++){
            pairs.push_back({i, j});
        }
    }
    while(pairs.size()%3) pairs.push_back({0, 0});
    for(int i=0; i<pairs.size(); i+=3){
        pair <int, int> a = pairs[i];
        pair <int, int> b = pairs[i+1];
        pair <int, int> c = pairs[i+2];
        int tr = 0;
        for(int j=0; j<5; j++){
            tr += (1 << j)*decode_bit();
        }
        info[a.first][a.second] = tr%3;
        tr /= 3;
        info[b.first][b.second] = tr%3;
        tr /= 3;
        info[c.first][c.second] = tr;
    }
    for(int i=0; i<nh; i++){
        dfs(0, -1, i);
        int dod = -dist[i][i];
        for(int j=0; j<nv; j++) dist[i][j] += dod;
        for(int j=0; j<nv; j++) hops(i, j, dist[i][j]);
    }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0; i<pairs.size(); i+=3){
      |                  ~^~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0; i<pairs.size(); i+=3){
      |                  ~^~~~~~~~~~~~~
decoder.cpp:25:9: warning: unused variable 'tr' [-Wunused-variable]
   25 |     int tr = 0;
      |         ^~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 12604 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 3 ms 5152 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 28 ms 7504 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 4 ms 5096 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 7688 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 40 ms 8004 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 61 ms 8212 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 7752 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 34 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 36 ms 7840 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 7796 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 59 ms 8148 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 50 ms 8200 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 63 ms 8456 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 44 ms 8012 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 74 ms 8728 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 107 ms 8836 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 70 ms 8500 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 109 ms 9204 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 12604 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 3 ms 5152 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 28 ms 7504 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 4 ms 5096 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 7688 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 40 ms 8004 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 61 ms 8212 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 7752 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 34 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 36 ms 7840 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 7796 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 59 ms 8148 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 50 ms 8200 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 63 ms 8456 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 44 ms 8012 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 74 ms 8728 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 107 ms 8836 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 70 ms 8500 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 109 ms 9204 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 12604 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 3 ms 5152 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 28 ms 7504 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 4 ms 5096 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 7688 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 40 ms 8004 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 61 ms 8212 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 7752 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 34 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 36 ms 7840 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 7796 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 59 ms 8148 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 50 ms 8200 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 63 ms 8456 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 44 ms 8012 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 74 ms 8728 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 107 ms 8836 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 70 ms 8500 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 109 ms 9204 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 12604 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 3 ms 5152 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 28 ms 7504 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 4 ms 5096 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 27 ms 7688 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 40 ms 8004 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 61 ms 8212 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 27 ms 7752 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 34 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 28 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 36 ms 7840 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 27 ms 7796 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 75 ms 8404 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 33 ms 7720 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 31 ms 7708 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 59 ms 8148 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 50 ms 8200 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 63 ms 8456 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 44 ms 8012 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 74 ms 8728 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 107 ms 8836 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 70 ms 8500 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 109 ms 9204 KB Output is correct - 69930 call(s) of encode_bit()