oj.uz

Submission #231998

# Submission time Handle Problem Language Result Execution time Memory
231998 2020-05-15T15:48:08 Z AlexLuchianov Saveit (IOI10_saveit) C++14
100 / 100
 361 ms 11504 KB 
#include "grader.h"
#include <vector>
#include <cmath>
#include <cassert>
#include <queue>

int const nmax = 1000;
int const kmax = 36;

using ll = long long;

std::vector<int> g[1 + nmax];

std::vector<int> bfs(int n, int node){
  std::vector<int> dist(n);
  std::queue<int> q;
  q.push(node);
  dist[node] = 1;
  while(0 < q.size()){
    int node = q.front();
    q.pop();
    for(int h = 0; h < g[node].size(); h++){
      int to = g[node][h];
      if(dist[to] == 0){
        dist[to] = dist[node] + 1;
        q.push(to);
      }
    }
  }
  for(int i = 0; i < n; i++)
    dist[i]--;
  return dist;
}

std::vector<int> dist[1 + kmax];
int far[1 + nmax];

int const necessary = 35 / 5 * 8;

void push(ll number, int bits){
  for(int i = 0; i < bits; i++)
    encode_bit(0 < (number & (1LL << i)));
}

void encode(int n, int k, int m, int *v1, int *v2){
  for(int i = 0; i < m; i++){
    int x = v1[i];
    int y = v2[i];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for(int i = 0; i < k; i++)
    dist[i] = bfs(n, i);

  for(int i = 1;i < n; i++){
    for(int h = 0; h < g[i].size(); h++){
      int to = g[i][h];
      if(dist[0][to] + 1 == dist[0][i]) {
        far[i] = to;
        push(to, 10);
        break;
      }
    }
  }

  for(int i = 1; i < n; i++){
    ll number = 0;
    int par = far[i];
    for(int h = 1; h < k; h++)
      number = number * 3 + (dist[h][i] - dist[h][par]) + 1;
    push(number, necessary);
  }

  return;
}

#include "grader.h"
#include <vector>


using ll = long long;
int const necessary = 35 / 5 * 8;
int const kmax = 40;
int const nmax = 1000;

int _far[1 + nmax];

ll extract(int bits){
  ll result = 0;
  for(int i = 0; i < bits; i++)
    result += decode_bit() * (1LL << i);
  return result;
}
std::vector<int> _g[1 + nmax];
int cost[1 + kmax][1 + nmax];
int dp[1 + kmax][1 + nmax];

void mark(int node, int era){
  for(int h = 0; h < _g[node].size(); h++){
    int to = _g[node][h];
    dp[era][to] = dp[era][node] + cost[era][to];
    mark(to, era);
  }
}


void decode(int n, int k) {

  for(int i = 1;i < n; i++) {
    _far[i] = extract(10);
    _g[_far[i]].push_back(i);
  }

  for(int i = 1; i < n; i++){
    ll number = extract(necessary);
    cost[0][i] = 1;
    for(int h = k - 1; 0 < h; h--){
      cost[h][i] = number % 3 - 1;
      number /= 3;
    }
  }

  for(int h = 0; h < k; h++) {
    mark(0, h);
    for(int i = 0; i < n; i++)
      hops(h, i, dp[h][i] - dp[h][h]);
  }
}

Compilation message

encoder.cpp: In function 'std::vector<int> bfs(int, int)':
encoder.cpp:22:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[node].size(); h++){
                    ~~^~~~~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[i].size(); h++){
                    ~~^~~~~~~~~~~~~

decoder.cpp: In function 'void mark(int, int)':
decoder.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int h = 0; h < _g[node].size(); h++){
                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 11504 KB Output is correct - 65934 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 264 call(s) of encode_bit()
3 Correct 33 ms 5752 KB Output is correct - 59334 call(s) of encode_bit()
4 Correct 12 ms 4768 KB Output is correct - 264 call(s) of encode_bit()
5 Correct 36 ms 6048 KB Output is correct - 59334 call(s) of encode_bit()
6 Correct 49 ms 6148 KB Output is correct - 65934 call(s) of encode_bit()
7 Correct 65 ms 6532 KB Output is correct - 65934 call(s) of encode_bit()
8 Correct 40 ms 5784 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 36 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
10 Correct 36 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
11 Correct 46 ms 6096 KB Output is correct - 65934 call(s) of encode_bit()
12 Correct 39 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
13 Correct 76 ms 6620 KB Output is correct - 65934 call(s) of encode_bit()
14 Correct 36 ms 6156 KB Output is correct - 65934 call(s) of encode_bit()
15 Correct 37 ms 6076 KB Output is correct - 65934 call(s) of encode_bit()
16 Correct 69 ms 6520 KB Output is correct - 65934 call(s) of encode_bit()
17 Correct 67 ms 6412 KB Output is correct - 65934 call(s) of encode_bit()
18 Correct 63 ms 6644 KB Output is correct - 65934 call(s) of encode_bit()
19 Correct 49 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
20 Correct 80 ms 7052 KB Output is correct - 65934 call(s) of encode_bit()
21 Correct 114 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()
22 Correct 55 ms 6524 KB Output is correct - 65934 call(s) of encode_bit()
23 Correct 90 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 11504 KB Output is correct - 65934 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 264 call(s) of encode_bit()
3 Correct 33 ms 5752 KB Output is correct - 59334 call(s) of encode_bit()
4 Correct 12 ms 4768 KB Output is correct - 264 call(s) of encode_bit()
5 Correct 36 ms 6048 KB Output is correct - 59334 call(s) of encode_bit()
6 Correct 49 ms 6148 KB Output is correct - 65934 call(s) of encode_bit()
7 Correct 65 ms 6532 KB Output is correct - 65934 call(s) of encode_bit()
8 Correct 40 ms 5784 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 36 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
10 Correct 36 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
11 Correct 46 ms 6096 KB Output is correct - 65934 call(s) of encode_bit()
12 Correct 39 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
13 Correct 76 ms 6620 KB Output is correct - 65934 call(s) of encode_bit()
14 Correct 36 ms 6156 KB Output is correct - 65934 call(s) of encode_bit()
15 Correct 37 ms 6076 KB Output is correct - 65934 call(s) of encode_bit()
16 Correct 69 ms 6520 KB Output is correct - 65934 call(s) of encode_bit()
17 Correct 67 ms 6412 KB Output is correct - 65934 call(s) of encode_bit()
18 Correct 63 ms 6644 KB Output is correct - 65934 call(s) of encode_bit()
19 Correct 49 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
20 Correct 80 ms 7052 KB Output is correct - 65934 call(s) of encode_bit()
21 Correct 114 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()
22 Correct 55 ms 6524 KB Output is correct - 65934 call(s) of encode_bit()
23 Correct 90 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 11504 KB Output is correct - 65934 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 264 call(s) of encode_bit()
3 Correct 33 ms 5752 KB Output is correct - 59334 call(s) of encode_bit()
4 Correct 12 ms 4768 KB Output is correct - 264 call(s) of encode_bit()
5 Correct 36 ms 6048 KB Output is correct - 59334 call(s) of encode_bit()
6 Correct 49 ms 6148 KB Output is correct - 65934 call(s) of encode_bit()
7 Correct 65 ms 6532 KB Output is correct - 65934 call(s) of encode_bit()
8 Correct 40 ms 5784 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 36 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
10 Correct 36 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
11 Correct 46 ms 6096 KB Output is correct - 65934 call(s) of encode_bit()
12 Correct 39 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
13 Correct 76 ms 6620 KB Output is correct - 65934 call(s) of encode_bit()
14 Correct 36 ms 6156 KB Output is correct - 65934 call(s) of encode_bit()
15 Correct 37 ms 6076 KB Output is correct - 65934 call(s) of encode_bit()
16 Correct 69 ms 6520 KB Output is correct - 65934 call(s) of encode_bit()
17 Correct 67 ms 6412 KB Output is correct - 65934 call(s) of encode_bit()
18 Correct 63 ms 6644 KB Output is correct - 65934 call(s) of encode_bit()
19 Correct 49 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
20 Correct 80 ms 7052 KB Output is correct - 65934 call(s) of encode_bit()
21 Correct 114 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()
22 Correct 55 ms 6524 KB Output is correct - 65934 call(s) of encode_bit()
23 Correct 90 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 11504 KB Output is correct - 65934 call(s) of encode_bit()
2 Correct 11 ms 4736 KB Output is correct - 264 call(s) of encode_bit()
3 Correct 33 ms 5752 KB Output is correct - 59334 call(s) of encode_bit()
4 Correct 12 ms 4768 KB Output is correct - 264 call(s) of encode_bit()
5 Correct 36 ms 6048 KB Output is correct - 59334 call(s) of encode_bit()
6 Correct 49 ms 6148 KB Output is correct - 65934 call(s) of encode_bit()
7 Correct 65 ms 6532 KB Output is correct - 65934 call(s) of encode_bit()
8 Correct 40 ms 5784 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 36 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
10 Correct 36 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
11 Correct 46 ms 6096 KB Output is correct - 65934 call(s) of encode_bit()
12 Correct 39 ms 6024 KB Output is correct - 65934 call(s) of encode_bit()
13 Correct 76 ms 6620 KB Output is correct - 65934 call(s) of encode_bit()
14 Correct 36 ms 6156 KB Output is correct - 65934 call(s) of encode_bit()
15 Correct 37 ms 6076 KB Output is correct - 65934 call(s) of encode_bit()
16 Correct 69 ms 6520 KB Output is correct - 65934 call(s) of encode_bit()
17 Correct 67 ms 6412 KB Output is correct - 65934 call(s) of encode_bit()
18 Correct 63 ms 6644 KB Output is correct - 65934 call(s) of encode_bit()
19 Correct 49 ms 6144 KB Output is correct - 65934 call(s) of encode_bit()
20 Correct 80 ms 7052 KB Output is correct - 65934 call(s) of encode_bit()
21 Correct 114 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()
22 Correct 55 ms 6524 KB Output is correct - 65934 call(s) of encode_bit()
23 Correct 90 ms 7160 KB Output is correct - 65934 call(s) of encode_bit()