oj.uz

Submission #860534

# Submission time Handle Problem Language Result Execution time Memory
860534 2023-10-13T07:59:29 Z nguyentunglam Saveit (IOI10_saveit) C++17
50 / 100
 221 ms 20524 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int f[N];

vector<int> adj[N];

void encode(int n, int h, int p, int *v1, int *v2){
   int T = log2(n) + 1;

   for(int i = 0; i < p; i++) {
      adj[v1[i]].push_back(v2[i]);
      adj[v2[i]].push_back(v1[i]);
   }

   for(int i = 0; i < h; i++) {
      for(int j = 0; j < n; j++) f[j] = -1;
      f[i] = 0;
      queue<int> q; q.push(i);
      while (!q.empty()) {
         int u = q.front(); q.pop();
         for(int &v : adj[u]) if (f[v] < 0) {
            f[v] = f[u] + 1;
            q.push(v);
         }
      }


      for(int j = 0; j < n; j++) {
         for(int k = 0; k < T; k++) encode_bit(f[j] >> k & 1);
      }
   }
}

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

void decode(int n, int h) {
   int T = log2(n) + 1;

   for(int i = 0; i < h; i++) for(int j = 0; j < n; j++) {
      int ans = 0;
      for(int k = 0; k < T; k++) if (decode_bit()) ans |= (1 << k);
//      if (i == 0 && j == 1) cout << ans << endl;
      hops(i, j, ans);
//      cout << i << " " << j << " " << ans << endl;
   }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 20524 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 45 call(s) of encode_bit()
3 Correct 53 ms 15376 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 52 ms 16288 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 57 ms 15984 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 65 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 54 ms 15496 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 54 ms 15932 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 54 ms 15384 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 55 ms 15704 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 54 ms 15316 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 85 ms 16340 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 54 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 62 ms 15556 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 82 ms 16060 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 64 ms 15740 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 72 ms 15904 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 65 ms 15588 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 98 ms 18336 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 95 ms 18592 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 79 ms 15628 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 94 ms 18632 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 20524 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 45 call(s) of encode_bit()
3 Correct 53 ms 15376 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 52 ms 16288 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 57 ms 15984 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 65 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 54 ms 15496 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 54 ms 15932 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 54 ms 15384 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 55 ms 15704 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 54 ms 15316 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 85 ms 16340 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 54 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 62 ms 15556 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 82 ms 16060 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 64 ms 15740 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 72 ms 15904 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 65 ms 15588 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 98 ms 18336 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 95 ms 18592 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 79 ms 15628 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 94 ms 18632 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 20524 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 45 call(s) of encode_bit()
3 Correct 53 ms 15376 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 52 ms 16288 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 57 ms 15984 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 65 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 54 ms 15496 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 54 ms 15932 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 54 ms 15384 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 55 ms 15704 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 54 ms 15316 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 85 ms 16340 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 54 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 62 ms 15556 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 82 ms 16060 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 64 ms 15740 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 72 ms 15904 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 65 ms 15588 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 98 ms 18336 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 95 ms 18592 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 79 ms 15628 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 94 ms 18632 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 20524 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 11268 KB Output is correct - 45 call(s) of encode_bit()
3 Correct 53 ms 15376 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 52 ms 16288 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 57 ms 15984 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 65 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 54 ms 15496 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 54 ms 15932 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 54 ms 15384 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 55 ms 15704 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 54 ms 15316 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 85 ms 16340 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 54 ms 15716 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 62 ms 15556 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 82 ms 16060 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 64 ms 15740 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 72 ms 15904 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 65 ms 15588 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 98 ms 18336 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 95 ms 18592 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 79 ms 15628 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 94 ms 18632 KB Output is partially correct - 360000 call(s) of encode_bit()