oj.uz

Submission #1017042

# Submission time Handle Problem Language Result Execution time Memory
1017042 2024-07-08T18:47:08 Z MilosMilutinovic Saveit (IOI10_saveit) C++14
0 / 100
 170 ms 16548 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

void encode(int nv, int nh, int ne, int *v1, int *v2) {
  vector<vector<int>> g(nv);
  for (int i = 0; i < ne; i++) {
    g[v1[i]].push_back(v2[i]);
    g[v2[i]].push_back(v1[i]);
  }
  vector<int> par(nv, -1);
  vector<bool> was(nv);
  function<void(int, int)> Dfs = [&](int v, int pv) {
    par[v] = pv;
    was[v] = true;
    for (int u : g[v]) {
      if (was[u]) {
        continue;
      }
      Dfs(u, v);
    }
  }; 
  Dfs(0, 0);
  for (int v = 0; v < nv; v++) {
    for (int b = 0; b < 10; b++) {
      encode_bit(par[v] >> b & 1);
    }
  }
  for (int h = 0; h < nh; h++) {
    vector<int> dist(nv, -1);
    dist[h] = 0;
    vector<int> que(1, h);
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : g[i]) {
        if (dist[j] == -1) {
          dist[j] = dist[i] + 1;
          que.push_back(j);
        }
      }
    }
    for (int v = 0; v < nv; v++) {
      if (dist[v] == dist[par[v]]) {
        encode_bit(0);
        encode_bit(0);
      }
      if (dist[v] == dist[par[v]] + 1) {
        encode_bit(0);
        encode_bit(1);
      }
      if (dist[v] == dist[par[v]] - 1) {
        encode_bit(1);
        encode_bit(0);
      }
    }
  }
  return;
}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

void decode(int nv, int nh) {
  vector<int> par(nv);
  for (int v = 0; v < nv; v++) {
    for (int b = 0; b < 10; b++) {
      if (decode_bit()) {
        par[v] += (1 << b);
      }
    }
  }
  vector<vector<int>> ch(nv);
  for (int i = 1; i < nv; i++) {
    ch[par[i]].push_back(i);
  }
  for (int h = 0; h < nh; h++) {
    vector<int> d(nv);
    for (int v = 0; v < nv; v++) {
      int t = 0;
      t += 2 * decode_bit();
      t += decode_bit();
      d[v] = (t == 0 ? 0 : (t == 1 ? 1 : -1));
    }
    vector<int> dist(nv, -1);
    dist[h] = 0;
    vector<int> que(1, h);
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : ch[i]) {
        if (dist[j] == -1) {
          dist[j] = dist[i] + d[i];
          que.push_back(j);
        }
      }
      if (dist[par[i]] == -1) {
        dist[par[i]] = dist[i] - d[i];
        que.push_back(par[i]);
      }
    }
    for (int v = 0; v < nv; v++) {
      hops(h, v, dist[v]);
    }
  }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 16548 KB wrong parameter
2 Incorrect 2 ms 11276 KB wrong parameter
3 Incorrect 12 ms 11524 KB wrong parameter
4 Incorrect 1 ms 11276 KB wrong parameter
5 Incorrect 13 ms 11532 KB wrong parameter
6 Incorrect 23 ms 11528 KB wrong parameter
7 Incorrect 23 ms 11756 KB wrong parameter
8 Incorrect 11 ms 11516 KB wrong parameter
9 Incorrect 12 ms 11268 KB wrong parameter
10 Incorrect 13 ms 11272 KB wrong parameter
11 Incorrect 13 ms 11528 KB wrong parameter
12 Incorrect 15 ms 11264 KB wrong parameter
13 Incorrect 28 ms 11932 KB wrong parameter
14 Incorrect 13 ms 11520 KB wrong parameter
15 Incorrect 18 ms 11520 KB wrong parameter
16 Incorrect 27 ms 11756 KB wrong parameter
17 Incorrect 27 ms 11784 KB wrong parameter
18 Incorrect 38 ms 11944 KB wrong parameter
19 Incorrect 18 ms 11776 KB wrong parameter
20 Incorrect 37 ms 14316 KB wrong parameter
21 Incorrect 54 ms 14316 KB wrong parameter
22 Incorrect 28 ms 11948 KB wrong parameter
23 Incorrect 46 ms 14616 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 16548 KB wrong parameter
2 Incorrect 2 ms 11276 KB wrong parameter
3 Incorrect 12 ms 11524 KB wrong parameter
4 Incorrect 1 ms 11276 KB wrong parameter
5 Incorrect 13 ms 11532 KB wrong parameter
6 Incorrect 23 ms 11528 KB wrong parameter
7 Incorrect 23 ms 11756 KB wrong parameter
8 Incorrect 11 ms 11516 KB wrong parameter
9 Incorrect 12 ms 11268 KB wrong parameter
10 Incorrect 13 ms 11272 KB wrong parameter
11 Incorrect 13 ms 11528 KB wrong parameter
12 Incorrect 15 ms 11264 KB wrong parameter
13 Incorrect 28 ms 11932 KB wrong parameter
14 Incorrect 13 ms 11520 KB wrong parameter
15 Incorrect 18 ms 11520 KB wrong parameter
16 Incorrect 27 ms 11756 KB wrong parameter
17 Incorrect 27 ms 11784 KB wrong parameter
18 Incorrect 38 ms 11944 KB wrong parameter
19 Incorrect 18 ms 11776 KB wrong parameter
20 Incorrect 37 ms 14316 KB wrong parameter
21 Incorrect 54 ms 14316 KB wrong parameter
22 Incorrect 28 ms 11948 KB wrong parameter
23 Incorrect 46 ms 14616 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 16548 KB wrong parameter
2 Incorrect 2 ms 11276 KB wrong parameter
3 Incorrect 12 ms 11524 KB wrong parameter
4 Incorrect 1 ms 11276 KB wrong parameter
5 Incorrect 13 ms 11532 KB wrong parameter
6 Incorrect 23 ms 11528 KB wrong parameter
7 Incorrect 23 ms 11756 KB wrong parameter
8 Incorrect 11 ms 11516 KB wrong parameter
9 Incorrect 12 ms 11268 KB wrong parameter
10 Incorrect 13 ms 11272 KB wrong parameter
11 Incorrect 13 ms 11528 KB wrong parameter
12 Incorrect 15 ms 11264 KB wrong parameter
13 Incorrect 28 ms 11932 KB wrong parameter
14 Incorrect 13 ms 11520 KB wrong parameter
15 Incorrect 18 ms 11520 KB wrong parameter
16 Incorrect 27 ms 11756 KB wrong parameter
17 Incorrect 27 ms 11784 KB wrong parameter
18 Incorrect 38 ms 11944 KB wrong parameter
19 Incorrect 18 ms 11776 KB wrong parameter
20 Incorrect 37 ms 14316 KB wrong parameter
21 Incorrect 54 ms 14316 KB wrong parameter
22 Incorrect 28 ms 11948 KB wrong parameter
23 Incorrect 46 ms 14616 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 16548 KB wrong parameter
2 Incorrect 2 ms 11276 KB wrong parameter
3 Incorrect 12 ms 11524 KB wrong parameter
4 Incorrect 1 ms 11276 KB wrong parameter
5 Incorrect 13 ms 11532 KB wrong parameter
6 Incorrect 23 ms 11528 KB wrong parameter
7 Incorrect 23 ms 11756 KB wrong parameter
8 Incorrect 11 ms 11516 KB wrong parameter
9 Incorrect 12 ms 11268 KB wrong parameter
10 Incorrect 13 ms 11272 KB wrong parameter
11 Incorrect 13 ms 11528 KB wrong parameter
12 Incorrect 15 ms 11264 KB wrong parameter
13 Incorrect 28 ms 11932 KB wrong parameter
14 Incorrect 13 ms 11520 KB wrong parameter
15 Incorrect 18 ms 11520 KB wrong parameter
16 Incorrect 27 ms 11756 KB wrong parameter
17 Incorrect 27 ms 11784 KB wrong parameter
18 Incorrect 38 ms 11944 KB wrong parameter
19 Incorrect 18 ms 11776 KB wrong parameter
20 Incorrect 37 ms 14316 KB wrong parameter
21 Incorrect 54 ms 14316 KB wrong parameter
22 Incorrect 28 ms 11948 KB wrong parameter
23 Incorrect 46 ms 14616 KB wrong parameter