oj.uz

Submission #599168

# Submission time Handle Problem Language Result Execution time Memory
599168 2022-07-19T11:15:08 Z Soumya1 Saveit (IOI10_saveit) C++17
100 / 100
 297 ms 10236 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1005;
vector<int> ad[mxN];
int par[mxN];
bool vis[mxN];
void dfs(int u) {
  vis[u] = true;
  for (int v : ad[u]) {
    if (vis[v]) continue;
    par[v] = u;
    dfs(v);
  }
}
vector<int> bfs(int s, int n) {
  vector<int> d(n, -1);
  queue<int> q;
  q.push(s);
  d[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : ad[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  return d;
}
map<int, vector<int>> seq;
map<vector<int>, int> id;
int cur;
void gen(vector<int> v) {
  if (v.size() == 5) {
    id[v] = cur;
    seq[cur] = v;
    cur++;
    return;
  }
  for (int i = -1; i <= 1; i++) {
    v.push_back(i);
    gen(v);
    v.pop_back();
  }
}
void encode(int n, int h, int m, int *v1, int *v2){
  for (int i = 0; i < m; i++) {
    ad[v1[i]].push_back(v2[i]);
    ad[v2[i]].push_back(v1[i]);
  }
  dfs(0);
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      encode_bit((par[i] >> j) & 1);
    }
  }
  gen({});
  for (int i = 0; i < h; i++) {
    auto d = bfs(i, n);
    for (int j = 0; j < 10; j++) {
      encode_bit((d[0] >> j) & 1);
    }
    vector<int> v;
    for (int j = 1; j < n; j++) {
      int del = d[j] - d[par[j]];
      v.push_back(del);
    }
    while (v.size() % 5 != 0) v.push_back(0);
    for (int k = 0; k < v.size(); k += 5) {
      vector<int> V;
      for (int j = k; j < k + 5; j++) V.push_back(v[j]);
      int val = id[V];
      for (int j = 0; j < 8; j++) encode_bit((val >> j) & 1);
    }
  }
  return;
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1010;
int p[mxN];
map<int, vector<int>> seqq;
map<vector<int>, int> idd;
int curr;
vector<int> adj[mxN];
int ans[mxN], del[mxN];
void dfs1(int u) {
  for (int v : adj[u]) {
    ans[v] = ans[u] + del[v];
    dfs1(v);
  }
}
void genn(vector<int> v) {
  if (v.size() == 5) {
    idd[v] = curr;
    seqq[curr] = v;
    curr++;
    return;
  }
  for (int i = -1; i <= 1; i++) {
    v.push_back(i);
    genn(v);
    v.pop_back();
  }
}
void decode(int n, int h) {
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      if (decode_bit()) p[i] |= (1 << j);
    }
  }
  for (int i = 1; i < n; i++) {
    adj[p[i]].push_back(i);
  }
  genn({});
  for (int i = 0; i < h; i++) {
    ans[0] = 0;
    for (int j = 0; j < 10; j++) {
      if (decode_bit()) ans[0] |= (1 << j);
    }
    int N = n - 1;
    while (N % 5 != 0) N++;
    for (int j = 0; j < N; j += 5) {
      int val = 0;
      for (int k = 0; k < 8; k++) {
        if (decode_bit()) val |= (1 << k);
      }
      auto v = seqq[val];
      for (int k = j; k < j + 5; k++) {
        if (k + 1 >= n) break;
        del[k + 1] = v[k - j];
      }
    }
    dfs1(0);
    for (int j = 0; j < n; j++) {
      hops(i, j, ans[j]);
    }
  }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int k = 0; k < v.size(); k += 5) {
      |                     ~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 10236 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 3 ms 4728 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 20 ms 5420 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 4 ms 4680 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 29 ms 5568 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 32 ms 5696 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 43 ms 5888 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 23 ms 5492 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 27 ms 5472 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 26 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 20 ms 5536 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 51 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 27 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 30 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 45 ms 5880 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 39 ms 5972 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 43 ms 6248 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 33 ms 5824 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 66 ms 6372 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 63 ms 6652 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 44 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 92 ms 6804 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 10236 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 3 ms 4728 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 20 ms 5420 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 4 ms 4680 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 29 ms 5568 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 32 ms 5696 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 43 ms 5888 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 23 ms 5492 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 27 ms 5472 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 26 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 20 ms 5536 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 51 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 27 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 30 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 45 ms 5880 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 39 ms 5972 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 43 ms 6248 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 33 ms 5824 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 66 ms 6372 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 63 ms 6652 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 44 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 92 ms 6804 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 10236 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 3 ms 4728 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 20 ms 5420 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 4 ms 4680 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 29 ms 5568 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 32 ms 5696 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 43 ms 5888 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 23 ms 5492 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 27 ms 5472 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 26 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 20 ms 5536 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 51 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 27 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 30 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 45 ms 5880 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 39 ms 5972 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 43 ms 6248 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 33 ms 5824 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 66 ms 6372 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 63 ms 6652 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 44 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 92 ms 6804 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 10236 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 3 ms 4728 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 20 ms 5420 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 4 ms 4680 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 29 ms 5568 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 32 ms 5696 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 43 ms 5888 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 23 ms 5492 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 31 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 27 ms 5472 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 26 ms 5768 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 20 ms 5536 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 51 ms 6080 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 27 ms 5480 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 30 ms 5624 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 45 ms 5880 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 39 ms 5972 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 43 ms 6248 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 33 ms 5824 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 66 ms 6372 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 63 ms 6652 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 44 ms 6092 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 92 ms 6804 KB Output is correct - 67950 call(s) of encode_bit()