Submission #444339

#	Time	Username	Problem	Language	Result	Execution time	Memory
444339		JovanB	Saveit (IOI10_saveit)	C++17	100 / 100	230 ms	12604 KiB

encoder

#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);
        }
    }
}

decoder

#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 (stderr)

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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25