Submission #623565

#	Time	Username	Problem	Language	Result	Execution time	Memory
623565		keta_tsimakuridze	Saveit (IOI10_saveit)	C++14	100 / 100	270 ms	10648 KiB

encoder

#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
#include "encoder.h"
const int N = 1002;
int d[N][40], p[N][40], f[3][3][3], n;
vector<int> V[N];
void bfs(int h) {

    for(int i = 0; i < n; i++) d[i][h] = n;
    d[h][h] = 0;
    queue<int> q;
    q.push(h);
    while(q.size()) {
        int u = q.front();
        q.pop();// cout <<  h << " " << u << " " << d[u][h] << endl;
        for(int i = 0; i < V[u].size(); i++) {
            if(d[V[u][i]][h] > d[u][h] + 1) {
                d[V[u][i]][h] = d[u][h] + 1;
                p[V[u][i]][h] = u;
                q.push(V[u][i]);
            }
        }
    }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
    n = nv;
    for(int i = 0; i < ne; i++) {
        V[v1[i]].push_back(v2[i]);
        V[v2[i]].push_back(v1[i]);
    }
    for(int i = 0; i < nh; i++)
    bfs(i);
    for(int i = 1; i < n; i++) {
        for(int j = 9; j >= 0; j--) {
            encode_bit(min(1, (1 << j) & p[i][0]));
        }
    }
    for(int T = 1; T < nh; T ++) {
        for(int i = 1; i < n; i += 3) {
            int u1 = i, v1 = p[i][0];
            int t1 = (d[u1][T] < d[v1][T] ? 2 : d[u1][T] > d[v1][T] ? 1 : 0);
            u1 = i + 1, v1 = (i + 1 >= n ? 0 : p[i + 1][0]);
            int t2 = (d[u1][T] < d[v1][T] ? 2 : d[u1][T] > d[v1][T] ? 1 : 0);
            u1 = i + 2, v1 = (i + 2 >= n ? 0 : p[i + 2][0]);
            int t3 = (d[u1][T] < d[v1][T] ? 2 : d[u1][T] > d[v1][T] ? 1 : 0);
            //if(T == 1 && i <= 4 && i + 3 > 4)cout <<"+++" << i << " " << t1  * 9 + t2 * 3 + t3 << endl;
            int x = t1 * 9 + t2 * 3 + t3;
            for(int i = 4; i >= 0; i--) encode_bit(min(1, (1 << i) & x));
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int M = 1005;
int D[M], di[40][M];
vector<pii> VV[M];
int nn;
void dfs(int u, int p, int H) {
    for(int i = 0; i < VV[u].size(); i++) {
        if(VV[u][i].f == p) continue;
        if(VV[u][i].s != u) D[VV[u][i].f] = D[u] + di[H][VV[u][i].s];
        else D[VV[u][i].f] = D[u] - di[H][VV[u][i].s];
        dfs(VV[u][i].f, u, H);
    }
}
void decode(int nv, int nh) {
    nn = nv;
    for(int i = 1; i < nn; i++) {
        int p = 0;
        for(int j = 9; j >= 0; j--) {
            p += (1 << j) * decode_bit();
        }
   //     cout << p << " --> " << i << endl;
        VV[i].push_back({p, i});
        VV[p].push_back({i, i});
        di[0][i] = 1;
    }
    for(int h = 1; h < nh; h++) {

        for(int i = 1; i < nn;  i += 3) {
            int t = 0;
            for(int j = 4; j >= 0; j--)
            t += (1 << j) * decode_bit();
            di[h][i] = (t / 9 == 2 ? -1 : t  / 9);
            di[h][i + 1] = (t / 3 % 3 == 2 ? -1 : t / 3 % 3);
            di[h][i + 2] = (t % 3 == 2 ? -1 : t % 3);
        }
    }
    for(int h = 0; h < nh; h++) {
        D[h] = 0;
        dfs(h, -1, h);
        for(int i = 0; i < nn; i++)   hops(h, i, D[i]);
    }
}

Compilation message (stderr)

encoder.cpp: In function 'void bfs(int)':
encoder.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(int i = 0; i < V[u].size(); i++) {
      |                        ~~^~~~~~~~~~~~~

decoder.cpp: In function 'void dfs(int, int, int)':
decoder.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < VV[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25