oj.uz

Submission #932870

# Submission time Handle Problem Language Result Execution time Memory
932870 2024-02-24T10:30:22 Z nguyentunglam Saveit (IOI10_saveit) C++17
100 / 100
 536 ms 25468 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;


namespace ENCODE {

const int NN = 1010;

int n, h;

int p[NN], d[NN][NN];

vector<int> adj[NN], _adj[NN];

void dfs(int u) {
  queue<int> q;
  for(int j = 0; j < n; j++) d[u][j] = -1;
  d[u][u] = 0;
  q.push(u);
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for(int &y : adj[x]) if (d[u][y] < 0) {
      d[u][y] = d[u][x] + 1;
      q.push(y);
    }
  }
  if (u) {
    long long val = 0;
    for(int j = 0; j < h; j++) {
      assert(abs(d[u][j] - d[p[u]][j]) <= 1);
      val = val * 3 + d[u][j] - d[p[u]][j] + 1;
    }
    for(int j = 0; j < 58; j++) encode_bit(val >> j & 1);
  }

  for(int &v : _adj[u]) dfs(v);
}

void encode(int N, int H, int m, int *v1, int *v2){
  n = N;
  h = H;
  for(int i = 0; i < m; i++) {
    adj[v1[i]].push_back(v2[i]);
    adj[v2[i]].push_back(v1[i]);
  }

  queue<int> q;
  q.push(0);
  for(int i = 1; i < n; i++) p[i] = -1;

  while (!q.empty()) {
    int u = q.front(); q.pop();
    for(int &v : adj[u]) if (p[v] < 0) {
      p[v] = u;
      q.push(v);
    }
  }

  for(int i = 1; i < n; i++) {
    for(int j = 0; j < 10; j++) encode_bit(p[i] >> j & 1);
    _adj[p[i]].push_back(i);
  }

  dfs(0);
}
}

void encode(int N, int H, int m, int *v1, int *v2) {
  ENCODE::encode(N, H, m, v1, v2);
}

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;

namespace DECODE {

const int NN = 1010;

int n, h;

int d[NN][NN], p[NN];

vector<int> adj[NN];

void dfs(int u) {
  if (u) {
    long long val = 0;
    for(int j = 0; j < 58; j++) if (decode_bit()) val |= (1LL << j);
    for(int j = h - 1; j >= 0; j--) {
      int diff = val % 3;
      d[u][j] = diff + d[p[u]][j] - 1;
      val /= 3;
    }
  }
  for(int j = 0; j < h; j++) {
    hops(j, u, d[u][j]);
  }
  for(int &v : adj[u]) dfs(v);
}

void decode(int nv, int nh) {
  n = nv;
  h = nh;
  for(int i = 1; i < n; i++) {
    for(int j = 0; j < 10; j++) if (decode_bit()) p[i] |= (1 << j);
    adj[p[i]].push_back(i);
  }

  for(int j = 1; j < h; j++) {
    int x = j;
    while (x) {
      d[0][j]++;
      x = p[x];
    }
  }

  dfs(0);
}
}

void decode(int nv, int nh)  {
  DECODE::decode(nv, nh);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 25468 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 2 ms 15360 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 47 ms 19856 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 15368 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 48 ms 20132 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 58 ms 20384 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 96 ms 20580 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 24 ms 20048 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 30 ms 20108 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 31 ms 20416 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 48 ms 20492 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 32 ms 20540 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 121 ms 20940 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 31 ms 20552 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 34 ms 20728 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 106 ms 21028 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 90 ms 20804 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 126 ms 20764 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 69 ms 20744 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 141 ms 23124 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 157 ms 23212 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 108 ms 21008 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 189 ms 23556 KB Output is correct - 67932 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 25468 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 2 ms 15360 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 47 ms 19856 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 15368 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 48 ms 20132 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 58 ms 20384 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 96 ms 20580 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 24 ms 20048 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 30 ms 20108 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 31 ms 20416 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 48 ms 20492 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 32 ms 20540 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 121 ms 20940 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 31 ms 20552 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 34 ms 20728 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 106 ms 21028 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 90 ms 20804 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 126 ms 20764 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 69 ms 20744 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 141 ms 23124 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 157 ms 23212 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 108 ms 21008 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 189 ms 23556 KB Output is correct - 67932 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 25468 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 2 ms 15360 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 47 ms 19856 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 15368 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 48 ms 20132 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 58 ms 20384 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 96 ms 20580 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 24 ms 20048 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 30 ms 20108 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 31 ms 20416 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 48 ms 20492 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 32 ms 20540 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 121 ms 20940 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 31 ms 20552 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 34 ms 20728 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 106 ms 21028 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 90 ms 20804 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 126 ms 20764 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 69 ms 20744 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 141 ms 23124 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 157 ms 23212 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 108 ms 21008 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 189 ms 23556 KB Output is correct - 67932 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 25468 KB Output is correct - 67932 call(s) of encode_bit()
2 Correct 2 ms 15360 KB Output is correct - 272 call(s) of encode_bit()
3 Correct 47 ms 19856 KB Output is correct - 61132 call(s) of encode_bit()
4 Correct 2 ms 15368 KB Output is correct - 272 call(s) of encode_bit()
5 Correct 48 ms 20132 KB Output is correct - 61132 call(s) of encode_bit()
6 Correct 58 ms 20384 KB Output is correct - 67932 call(s) of encode_bit()
7 Correct 96 ms 20580 KB Output is correct - 67932 call(s) of encode_bit()
8 Correct 24 ms 20048 KB Output is correct - 65280 call(s) of encode_bit()
9 Correct 30 ms 20108 KB Output is correct - 67932 call(s) of encode_bit()
10 Correct 31 ms 20416 KB Output is correct - 67932 call(s) of encode_bit()
11 Correct 48 ms 20492 KB Output is correct - 67932 call(s) of encode_bit()
12 Correct 32 ms 20540 KB Output is correct - 67932 call(s) of encode_bit()
13 Correct 121 ms 20940 KB Output is correct - 67932 call(s) of encode_bit()
14 Correct 31 ms 20552 KB Output is correct - 67932 call(s) of encode_bit()
15 Correct 34 ms 20728 KB Output is correct - 67932 call(s) of encode_bit()
16 Correct 106 ms 21028 KB Output is correct - 67932 call(s) of encode_bit()
17 Correct 90 ms 20804 KB Output is correct - 67932 call(s) of encode_bit()
18 Correct 126 ms 20764 KB Output is correct - 67932 call(s) of encode_bit()
19 Correct 69 ms 20744 KB Output is correct - 67932 call(s) of encode_bit()
20 Correct 141 ms 23124 KB Output is correct - 67932 call(s) of encode_bit()
21 Correct 157 ms 23212 KB Output is correct - 67932 call(s) of encode_bit()
22 Correct 108 ms 21008 KB Output is correct - 67932 call(s) of encode_bit()
23 Correct 189 ms 23556 KB Output is correct - 67932 call(s) of encode_bit()