oj.uz

답안 #514909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
514909 2022-01-18T19:00:34 Z 600Mihnea 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 253 ms 10740 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) {
  const int STORING_BITS = 10;

  vector<vector<int>> g(nv);
  vector<int> parrent(nv, -2);
  vector<bool> vis(nv, 0);
  for (int i = 0; i < ne; i++) {
    g[v1[i]].push_back(v2[i]);
    g[v2[i]].push_back(v1[i]);
  }
  function<void(int)> dfs = [&] (int a) {
    vis[a] = 1;
    for (auto &b : g[a]) {
      if (!vis[b]) {
        parrent[b] = a;
        dfs(b);
      }
    }
  };
  parrent[0] = -1;
  dfs(0);
  int cnt = 0;
  for (int i = 1; i < nv; i++) {
    for (int bit = 0; bit < STORING_BITS; bit++) {
      if (parrent[i] & (1 << bit)) {
        encode_bit(1);
        cnt++;
      } else {
        encode_bit(0);
        cnt++;
      }
    }
  }
  vector<int> stored;
  for (int i = 0; i < nh; i++) {
    /// calculate the dist from vertex i
    vector<int> d(nv, -1);
    queue<int> q;
    q.push(i);
    d[i] = 0;
    while (!q.empty()) {
      int a = q.front();
      q.pop();
      for (auto &b : g[a]) {
        if (d[b] == -1) {
          d[b] = 1 + d[a];
          q.push(b);
        }
      }
    }

    for (int i = 1; i < nv; i++) {
      int dif = d[i] - d[parrent[i]];
      stored.push_back(dif + 1);
    }
  }

  for (auto &send : stored) {
    if (send == 0) {
      encode_bit(0);
      encode_bit(0);
    }
    if (send == 1) {
      encode_bit(0);
      encode_bit(1);
    }
    if (send == 2) {
      encode_bit(1);
      encode_bit(0);
    }
  }
}


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

using namespace std;

void decode(int nv, int nh) {
  const int STORING_BITS = 10;
  vector<int> parrent(nv, 0);
  parrent[0] = -1;
  for (int i = 1; i < nv; i++) {
    for (int bit = 0; bit < STORING_BITS; bit++) {
      int x = decode_bit();
      parrent[i] += (1 << bit) * x;
    }
  }

  vector<int> stored(nh * (nv - 1));
  for (int i = 0; i < (int) stored.size(); i++) {
    int a = decode_bit();
    int b = decode_bit();
    if (a == 0) {
      stored[i] = b;
    } else {
      stored[i] = 2;
    }
  }
  int po = 0;
  for (int r = 0; r < nh; r++) {
    /// calculate the dist from vertex i
    vector<vector<pair<int, int>>> g(nv);
    for (int i = 1; i < nv; i++) {
      int dif = stored[po++] - 1;
      int j = parrent[i];
      g[i].push_back({j, dif});
      g[j].push_back({i, -dif});
    }
    const int TOKEN = -(int) 1e9;
    vector<int> sol(nv, TOKEN);
    sol[r] = 0;
    function<void(int)> explore = [&] (int a) {
      for (auto &b : g[a]) {
        if (sol[b.first] == TOKEN) {
          sol[b.first] = sol[a] - b.second;
          explore(b.first);
        }
      }
    };
    explore(r);
    if (r == 0) {
      sol[1] = 100;
    }
    for (int i = 0; i < nv; i++) {
      hops(r, i, sol[i]);
    }
  }
}

Subtask #1
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 253 ms 10740 KB Output isn't correct
2 Incorrect 1 ms 4452 KB wrong parameter
3 Incorrect 23 ms 5872 KB Output isn't correct
4 Incorrect 2 ms 4576 KB wrong parameter
5 Incorrect 36 ms 5972 KB Output isn't correct
6 Incorrect 30 ms 6140 KB Output isn't correct
7 Incorrect 51 ms 6552 KB Output isn't correct
8 Incorrect 24 ms 5876 KB Output isn't correct
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 29 ms 5944 KB Output isn't correct
11 Incorrect 32 ms 6108 KB Output isn't correct
12 Incorrect 24 ms 5868 KB Output isn't correct
13 Incorrect 52 ms 6548 KB Output isn't correct
14 Incorrect 27 ms 5924 KB Output isn't correct
15 Incorrect 31 ms 5992 KB Output isn't correct
16 Incorrect 61 ms 6332 KB Output isn't correct
17 Incorrect 53 ms 6456 KB Output isn't correct
18 Incorrect 52 ms 6576 KB Output isn't correct
19 Incorrect 33 ms 6284 KB Output isn't correct
20 Incorrect 65 ms 6948 KB Output isn't correct
21 Incorrect 66 ms 7312 KB Output isn't correct
22 Incorrect 69 ms 6520 KB Output isn't correct
23 Incorrect 94 ms 7360 KB Output isn't correct

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 253 ms 10740 KB Output isn't correct
2 Incorrect 1 ms 4452 KB wrong parameter
3 Incorrect 23 ms 5872 KB Output isn't correct
4 Incorrect 2 ms 4576 KB wrong parameter
5 Incorrect 36 ms 5972 KB Output isn't correct
6 Incorrect 30 ms 6140 KB Output isn't correct
7 Incorrect 51 ms 6552 KB Output isn't correct
8 Incorrect 24 ms 5876 KB Output isn't correct
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 29 ms 5944 KB Output isn't correct
11 Incorrect 32 ms 6108 KB Output isn't correct
12 Incorrect 24 ms 5868 KB Output isn't correct
13 Incorrect 52 ms 6548 KB Output isn't correct
14 Incorrect 27 ms 5924 KB Output isn't correct
15 Incorrect 31 ms 5992 KB Output isn't correct
16 Incorrect 61 ms 6332 KB Output isn't correct
17 Incorrect 53 ms 6456 KB Output isn't correct
18 Incorrect 52 ms 6576 KB Output isn't correct
19 Incorrect 33 ms 6284 KB Output isn't correct
20 Incorrect 65 ms 6948 KB Output isn't correct
21 Incorrect 66 ms 7312 KB Output isn't correct
22 Incorrect 69 ms 6520 KB Output isn't correct
23 Incorrect 94 ms 7360 KB Output isn't correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 253 ms 10740 KB Output isn't correct
2 Incorrect 1 ms 4452 KB wrong parameter
3 Incorrect 23 ms 5872 KB Output isn't correct
4 Incorrect 2 ms 4576 KB wrong parameter
5 Incorrect 36 ms 5972 KB Output isn't correct
6 Incorrect 30 ms 6140 KB Output isn't correct
7 Incorrect 51 ms 6552 KB Output isn't correct
8 Incorrect 24 ms 5876 KB Output isn't correct
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 29 ms 5944 KB Output isn't correct
11 Incorrect 32 ms 6108 KB Output isn't correct
12 Incorrect 24 ms 5868 KB Output isn't correct
13 Incorrect 52 ms 6548 KB Output isn't correct
14 Incorrect 27 ms 5924 KB Output isn't correct
15 Incorrect 31 ms 5992 KB Output isn't correct
16 Incorrect 61 ms 6332 KB Output isn't correct
17 Incorrect 53 ms 6456 KB Output isn't correct
18 Incorrect 52 ms 6576 KB Output isn't correct
19 Incorrect 33 ms 6284 KB Output isn't correct
20 Incorrect 65 ms 6948 KB Output isn't correct
21 Incorrect 66 ms 7312 KB Output isn't correct
22 Incorrect 69 ms 6520 KB Output isn't correct
23 Incorrect 94 ms 7360 KB Output isn't correct

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 253 ms 10740 KB Output isn't correct
2 Incorrect 1 ms 4452 KB wrong parameter
3 Incorrect 23 ms 5872 KB Output isn't correct
4 Incorrect 2 ms 4576 KB wrong parameter
5 Incorrect 36 ms 5972 KB Output isn't correct
6 Incorrect 30 ms 6140 KB Output isn't correct
7 Incorrect 51 ms 6552 KB Output isn't correct
8 Incorrect 24 ms 5876 KB Output isn't correct
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 29 ms 5944 KB Output isn't correct
11 Incorrect 32 ms 6108 KB Output isn't correct
12 Incorrect 24 ms 5868 KB Output isn't correct
13 Incorrect 52 ms 6548 KB Output isn't correct
14 Incorrect 27 ms 5924 KB Output isn't correct
15 Incorrect 31 ms 5992 KB Output isn't correct
16 Incorrect 61 ms 6332 KB Output isn't correct
17 Incorrect 53 ms 6456 KB Output isn't correct
18 Incorrect 52 ms 6576 KB Output isn't correct
19 Incorrect 33 ms 6284 KB Output isn't correct
20 Incorrect 65 ms 6948 KB Output isn't correct
21 Incorrect 66 ms 7312 KB Output isn't correct
22 Incorrect 69 ms 6520 KB Output isn't correct
23 Incorrect 94 ms 7360 KB Output isn't correct