oj.uz

Submission #272115

# Submission time Handle Problem Language Result Execution time Memory
272115 2020-08-18T09:11:38 Z sjimed Saveit (IOI10_saveit) C++14
0 / 100
 250 ms 11760 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;

static int n, h, m;
static int ans[40][1010];
static vector<int> g[1010];
static int pre[1010];
static bool chk[1010];

static void dfs(int x) {
  chk[x] = true;
  for(auto i : g[x]) {
    if(chk[i]) continue;

    pre[i] = x;
    dfs(i);
  }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  n = nv;
  h = nh;
  m = ne;

  for(int i=0; i<m; i++) {
    g[v1[i]].eb(v2[i]);
    g[v2[i]].eb(v1[i]);
  }

  dfs(0);

  for(int i=0; i<n; i++) {
    for(int j=0; j<10; j++) {
      if(pre[i] & (1<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }

  for(int s=0; s<h; s++) {
    queue<int> q;

    q.em(s);
    ans[s][s] = 1;

    while(q.size()) {
      int x = q.front();
      q.pop();

      for(auto i : g[x]) {
        if(ans[s][i]) continue;

        ans[s][i] = ans[s][x] + 1;
        q.em(i);
      }
    }
  }

  for(int i=0; i<h; i++) {
    for(int j=0; j<n; j++) {
      ans[i][j]--;
    }
  }

  for(int i=0; i<h; i++) {
    for(int j=1; j < n; ) {
      int t = 0;
      for(int k=0; k < 5; k++) {
        t *= 3;
        t += (ans[i][j+k] - ans[i][pre[j + k]]) + 1;
      }
     
      for(int k=0; k<8; k++) {
        if(t & (1<<k)) encode_bit(1);
        else encode_bit(0);
      }

      j += 5;
    }
  }

  for(int i=0; i<h; i++) {
    for(int j=0; j<10; j++) {
      if(ans[i][0] & (1<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }
}

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

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define em emplace
#define eb emplace_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const int inf = 1e9;

static int n, h;
static int pre[1010];
static int ans[40][1110];
static vector<int> g[1010];

static void dfs(int x) {
   for(auto i : g[x]) {
      for(int j=0; j<h; j++) 
         ans[j][i] += ans[j][x];
      
      dfs(i);
   }
}

void decode(int nv, int nh) {
   n = nv;
   h = nh;

   for(int i=0; i<n; i++) {
      int b = 0;
      for(int j=0; j<10; j++) {
         if(decode_bit()) b |= 1<<j;
      }

      pre[i] = b;
      if(i) g[pre[i]].eb(i);
   }

   for(int i=0; i<h; i++) {
      for(int j=1; j<n; ) {
         int d = 0;
         for(int k=0; k<8; k++) {
            if(decode_bit()) d |= (1 << k);
         }

         for(int k=4; k>=0; k--) {
            ans[i][j+k] = d % 3 - 1;
            d /= 3;
         }

         j += 5;
      }
   }

   for(int i=0; i<h; i++) {
      for(int j=0; j<10; j++) {
         if(decode_bit()) ans[i][0] |= 1 << j;
      }
   }

   dfs(0);

   for(int i=0; i<h; i++) {
      for(int j=0; j<n; j++) {
         hops(i, j, ans[i][j]);
      }
   }
}

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 11760 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5892 KB Output isn't correct
4 Correct 4 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 36 ms 6016 KB Output isn't correct
6 Incorrect 39 ms 5888 KB Output isn't correct
7 Incorrect 49 ms 6432 KB Output isn't correct
8 Correct 28 ms 5968 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 30 ms 5804 KB Output isn't correct
10 Incorrect 27 ms 5952 KB wrong parameter
11 Incorrect 40 ms 6084 KB Output isn't correct
12 Incorrect 27 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6524 KB wrong parameter
14 Incorrect 37 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 6000 KB Output isn't correct
16 Incorrect 86 ms 6440 KB wrong parameter
17 Incorrect 74 ms 6392 KB wrong parameter
18 Incorrect 76 ms 6588 KB wrong parameter
19 Incorrect 44 ms 6264 KB wrong parameter
20 Incorrect 64 ms 7040 KB wrong parameter
21 Incorrect 88 ms 7104 KB wrong parameter
22 Incorrect 88 ms 6392 KB wrong parameter
23 Incorrect 60 ms 7428 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 11760 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5892 KB Output isn't correct
4 Correct 4 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 36 ms 6016 KB Output isn't correct
6 Incorrect 39 ms 5888 KB Output isn't correct
7 Incorrect 49 ms 6432 KB Output isn't correct
8 Correct 28 ms 5968 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 30 ms 5804 KB Output isn't correct
10 Incorrect 27 ms 5952 KB wrong parameter
11 Incorrect 40 ms 6084 KB Output isn't correct
12 Incorrect 27 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6524 KB wrong parameter
14 Incorrect 37 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 6000 KB Output isn't correct
16 Incorrect 86 ms 6440 KB wrong parameter
17 Incorrect 74 ms 6392 KB wrong parameter
18 Incorrect 76 ms 6588 KB wrong parameter
19 Incorrect 44 ms 6264 KB wrong parameter
20 Incorrect 64 ms 7040 KB wrong parameter
21 Incorrect 88 ms 7104 KB wrong parameter
22 Incorrect 88 ms 6392 KB wrong parameter
23 Incorrect 60 ms 7428 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 11760 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5892 KB Output isn't correct
4 Correct 4 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 36 ms 6016 KB Output isn't correct
6 Incorrect 39 ms 5888 KB Output isn't correct
7 Incorrect 49 ms 6432 KB Output isn't correct
8 Correct 28 ms 5968 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 30 ms 5804 KB Output isn't correct
10 Incorrect 27 ms 5952 KB wrong parameter
11 Incorrect 40 ms 6084 KB Output isn't correct
12 Incorrect 27 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6524 KB wrong parameter
14 Incorrect 37 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 6000 KB Output isn't correct
16 Incorrect 86 ms 6440 KB wrong parameter
17 Incorrect 74 ms 6392 KB wrong parameter
18 Incorrect 76 ms 6588 KB wrong parameter
19 Incorrect 44 ms 6264 KB wrong parameter
20 Incorrect 64 ms 7040 KB wrong parameter
21 Incorrect 88 ms 7104 KB wrong parameter
22 Incorrect 88 ms 6392 KB wrong parameter
23 Incorrect 60 ms 7428 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 11760 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5892 KB Output isn't correct
4 Correct 4 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 36 ms 6016 KB Output isn't correct
6 Incorrect 39 ms 5888 KB Output isn't correct
7 Incorrect 49 ms 6432 KB Output isn't correct
8 Correct 28 ms 5968 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 30 ms 5804 KB Output isn't correct
10 Incorrect 27 ms 5952 KB wrong parameter
11 Incorrect 40 ms 6084 KB Output isn't correct
12 Incorrect 27 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6524 KB wrong parameter
14 Incorrect 37 ms 5888 KB Output isn't correct
15 Incorrect 38 ms 6000 KB Output isn't correct
16 Incorrect 86 ms 6440 KB wrong parameter
17 Incorrect 74 ms 6392 KB wrong parameter
18 Incorrect 76 ms 6588 KB wrong parameter
19 Incorrect 44 ms 6264 KB wrong parameter
20 Incorrect 64 ms 7040 KB wrong parameter
21 Incorrect 88 ms 7104 KB wrong parameter
22 Incorrect 88 ms 6392 KB wrong parameter
23 Incorrect 60 ms 7428 KB wrong parameter