oj.uz

Submission #272112

# Submission time Handle Problem Language Result Execution time Memory
272112 2020-08-18T09:07:15 Z sjimed Saveit (IOI10_saveit) C++14
0 / 100
 268 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];

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 268 ms 11760 KB Output isn't correct
2 Correct 3 ms 4804 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 25 ms 5824 KB Output isn't correct
4 Correct 2 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 30 ms 6180 KB Output isn't correct
6 Incorrect 34 ms 6268 KB Output isn't correct
7 Incorrect 53 ms 6452 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 27 ms 5992 KB wrong parameter
11 Incorrect 35 ms 6068 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 51 ms 6520 KB wrong parameter
14 Incorrect 32 ms 5944 KB Output isn't correct
15 Incorrect 28 ms 5988 KB Output isn't correct
16 Incorrect 50 ms 6436 KB wrong parameter
17 Incorrect 53 ms 6492 KB wrong parameter
18 Incorrect 59 ms 6712 KB wrong parameter
19 Incorrect 37 ms 6392 KB wrong parameter
20 Incorrect 69 ms 6776 KB wrong parameter
21 Incorrect 84 ms 7084 KB wrong parameter
22 Incorrect 70 ms 6748 KB wrong parameter
23 Incorrect 75 ms 7300 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 11760 KB Output isn't correct
2 Correct 3 ms 4804 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 25 ms 5824 KB Output isn't correct
4 Correct 2 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 30 ms 6180 KB Output isn't correct
6 Incorrect 34 ms 6268 KB Output isn't correct
7 Incorrect 53 ms 6452 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 27 ms 5992 KB wrong parameter
11 Incorrect 35 ms 6068 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 51 ms 6520 KB wrong parameter
14 Incorrect 32 ms 5944 KB Output isn't correct
15 Incorrect 28 ms 5988 KB Output isn't correct
16 Incorrect 50 ms 6436 KB wrong parameter
17 Incorrect 53 ms 6492 KB wrong parameter
18 Incorrect 59 ms 6712 KB wrong parameter
19 Incorrect 37 ms 6392 KB wrong parameter
20 Incorrect 69 ms 6776 KB wrong parameter
21 Incorrect 84 ms 7084 KB wrong parameter
22 Incorrect 70 ms 6748 KB wrong parameter
23 Incorrect 75 ms 7300 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 11760 KB Output isn't correct
2 Correct 3 ms 4804 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 25 ms 5824 KB Output isn't correct
4 Correct 2 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 30 ms 6180 KB Output isn't correct
6 Incorrect 34 ms 6268 KB Output isn't correct
7 Incorrect 53 ms 6452 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 27 ms 5992 KB wrong parameter
11 Incorrect 35 ms 6068 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 51 ms 6520 KB wrong parameter
14 Incorrect 32 ms 5944 KB Output isn't correct
15 Incorrect 28 ms 5988 KB Output isn't correct
16 Incorrect 50 ms 6436 KB wrong parameter
17 Incorrect 53 ms 6492 KB wrong parameter
18 Incorrect 59 ms 6712 KB wrong parameter
19 Incorrect 37 ms 6392 KB wrong parameter
20 Incorrect 69 ms 6776 KB wrong parameter
21 Incorrect 84 ms 7084 KB wrong parameter
22 Incorrect 70 ms 6748 KB wrong parameter
23 Incorrect 75 ms 7300 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 11760 KB Output isn't correct
2 Correct 3 ms 4804 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 25 ms 5824 KB Output isn't correct
4 Correct 2 ms 4780 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 30 ms 6180 KB Output isn't correct
6 Incorrect 34 ms 6268 KB Output isn't correct
7 Incorrect 53 ms 6452 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 28 ms 5760 KB Output isn't correct
10 Incorrect 27 ms 5992 KB wrong parameter
11 Incorrect 35 ms 6068 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 51 ms 6520 KB wrong parameter
14 Incorrect 32 ms 5944 KB Output isn't correct
15 Incorrect 28 ms 5988 KB Output isn't correct
16 Incorrect 50 ms 6436 KB wrong parameter
17 Incorrect 53 ms 6492 KB wrong parameter
18 Incorrect 59 ms 6712 KB wrong parameter
19 Incorrect 37 ms 6392 KB wrong parameter
20 Incorrect 69 ms 6776 KB wrong parameter
21 Incorrect 84 ms 7084 KB wrong parameter
22 Incorrect 70 ms 6748 KB wrong parameter
23 Incorrect 75 ms 7300 KB wrong parameter