oj.uz

Submission #623565

# Submission time Handle Problem Language Result Execution time Memory
623565 2022-08-06T00:13:37 Z keta_tsimakuridze Saveit (IOI10_saveit) C++14
100 / 100
 270 ms 10648 KB 
#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));
        }
    }
}

#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10648 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 25 ms 5892 KB Output is correct - 61490 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 28 ms 6040 KB Output is correct - 61490 call(s) of encode_bit()
6 Correct 27 ms 5972 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 41 ms 6320 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 24 ms 5736 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 22 ms 5916 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 22 ms 5796 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 31 ms 6052 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 19 ms 6020 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 54 ms 6468 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 26 ms 5892 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 32 ms 5900 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 46 ms 6424 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 43 ms 6356 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 55 ms 6524 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 30 ms 6244 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 58 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 67 ms 6916 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 45 ms 6568 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 72 ms 7248 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10648 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 25 ms 5892 KB Output is correct - 61490 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 28 ms 6040 KB Output is correct - 61490 call(s) of encode_bit()
6 Correct 27 ms 5972 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 41 ms 6320 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 24 ms 5736 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 22 ms 5916 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 22 ms 5796 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 31 ms 6052 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 19 ms 6020 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 54 ms 6468 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 26 ms 5892 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 32 ms 5900 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 46 ms 6424 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 43 ms 6356 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 55 ms 6524 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 30 ms 6244 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 58 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 67 ms 6916 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 45 ms 6568 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 72 ms 7248 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10648 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 25 ms 5892 KB Output is correct - 61490 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 28 ms 6040 KB Output is correct - 61490 call(s) of encode_bit()
6 Correct 27 ms 5972 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 41 ms 6320 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 24 ms 5736 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 22 ms 5916 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 22 ms 5796 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 31 ms 6052 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 19 ms 6020 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 54 ms 6468 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 26 ms 5892 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 32 ms 5900 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 46 ms 6424 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 43 ms 6356 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 55 ms 6524 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 30 ms 6244 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 58 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 67 ms 6916 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 45 ms 6568 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 72 ms 7248 KB Output is correct - 68265 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10648 KB Output is correct - 68265 call(s) of encode_bit()
2 Correct 2 ms 4612 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 25 ms 5892 KB Output is correct - 61490 call(s) of encode_bit()
4 Correct 2 ms 4612 KB Output is correct - 80 call(s) of encode_bit()
5 Correct 28 ms 6040 KB Output is correct - 61490 call(s) of encode_bit()
6 Correct 27 ms 5972 KB Output is correct - 68265 call(s) of encode_bit()
7 Correct 41 ms 6320 KB Output is correct - 68265 call(s) of encode_bit()
8 Correct 24 ms 5736 KB Output is correct - 65600 call(s) of encode_bit()
9 Correct 22 ms 5916 KB Output is correct - 68265 call(s) of encode_bit()
10 Correct 22 ms 5796 KB Output is correct - 68265 call(s) of encode_bit()
11 Correct 31 ms 6052 KB Output is correct - 68265 call(s) of encode_bit()
12 Correct 19 ms 6020 KB Output is correct - 68265 call(s) of encode_bit()
13 Correct 54 ms 6468 KB Output is correct - 68265 call(s) of encode_bit()
14 Correct 26 ms 5892 KB Output is correct - 68265 call(s) of encode_bit()
15 Correct 32 ms 5900 KB Output is correct - 68265 call(s) of encode_bit()
16 Correct 46 ms 6424 KB Output is correct - 68265 call(s) of encode_bit()
17 Correct 43 ms 6356 KB Output is correct - 68265 call(s) of encode_bit()
18 Correct 55 ms 6524 KB Output is correct - 68265 call(s) of encode_bit()
19 Correct 30 ms 6244 KB Output is correct - 68265 call(s) of encode_bit()
20 Correct 58 ms 7032 KB Output is correct - 68265 call(s) of encode_bit()
21 Correct 67 ms 6916 KB Output is correct - 68265 call(s) of encode_bit()
22 Correct 45 ms 6568 KB Output is correct - 68265 call(s) of encode_bit()
23 Correct 72 ms 7248 KB Output is correct - 68265 call(s) of encode_bit()