oj.uz

Submission #272127

# Submission time Handle Problem Language Result Execution time Memory
272127 2020-08-18T09:35:22 Z sjimed Saveit (IOI10_saveit) C++14
0 / 100
 244 ms 11848 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 p[1010];
static bool chk[1010];

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

    p[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(p[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; j+=5) {
      
      int t = 0;
      for(int k=0; k < 5; k++) {
        t *= 3;
        t += (ans[i][j+k] - ans[i][p[j + k]]) + 1;
      }
     
      for(int k=0; k<8; k++) {
        if(t & (1<<k)) encode_bit(1);
        else encode_bit(0);
      }
    }
  }

  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 p[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;
      }

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

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

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

   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 244 ms 11848 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5984 KB Output isn't correct
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 37 ms 5888 KB Output isn't correct
6 Incorrect 31 ms 6276 KB Output isn't correct
7 Incorrect 49 ms 6392 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 31 ms 5820 KB Output isn't correct
10 Incorrect 26 ms 5760 KB wrong parameter
11 Incorrect 37 ms 6060 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6520 KB wrong parameter
14 Incorrect 31 ms 5956 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 51 ms 6476 KB wrong parameter
17 Incorrect 48 ms 6360 KB wrong parameter
18 Incorrect 62 ms 6720 KB wrong parameter
19 Incorrect 36 ms 6144 KB wrong parameter
20 Incorrect 67 ms 6944 KB wrong parameter
21 Incorrect 80 ms 7032 KB wrong parameter
22 Incorrect 89 ms 6580 KB wrong parameter
23 Incorrect 87 ms 7160 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 11848 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5984 KB Output isn't correct
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 37 ms 5888 KB Output isn't correct
6 Incorrect 31 ms 6276 KB Output isn't correct
7 Incorrect 49 ms 6392 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 31 ms 5820 KB Output isn't correct
10 Incorrect 26 ms 5760 KB wrong parameter
11 Incorrect 37 ms 6060 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6520 KB wrong parameter
14 Incorrect 31 ms 5956 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 51 ms 6476 KB wrong parameter
17 Incorrect 48 ms 6360 KB wrong parameter
18 Incorrect 62 ms 6720 KB wrong parameter
19 Incorrect 36 ms 6144 KB wrong parameter
20 Incorrect 67 ms 6944 KB wrong parameter
21 Incorrect 80 ms 7032 KB wrong parameter
22 Incorrect 89 ms 6580 KB wrong parameter
23 Incorrect 87 ms 7160 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 11848 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5984 KB Output isn't correct
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 37 ms 5888 KB Output isn't correct
6 Incorrect 31 ms 6276 KB Output isn't correct
7 Incorrect 49 ms 6392 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 31 ms 5820 KB Output isn't correct
10 Incorrect 26 ms 5760 KB wrong parameter
11 Incorrect 37 ms 6060 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6520 KB wrong parameter
14 Incorrect 31 ms 5956 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 51 ms 6476 KB wrong parameter
17 Incorrect 48 ms 6360 KB wrong parameter
18 Incorrect 62 ms 6720 KB wrong parameter
19 Incorrect 36 ms 6144 KB wrong parameter
20 Incorrect 67 ms 6944 KB wrong parameter
21 Incorrect 80 ms 7032 KB wrong parameter
22 Incorrect 89 ms 6580 KB wrong parameter
23 Incorrect 87 ms 7160 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 11848 KB Output isn't correct
2 Correct 4 ms 4736 KB Output is correct - 104 call(s) of encode_bit()
3 Incorrect 27 ms 5984 KB Output isn't correct
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Incorrect 37 ms 5888 KB Output isn't correct
6 Incorrect 31 ms 6276 KB Output isn't correct
7 Incorrect 49 ms 6392 KB Output isn't correct
8 Correct 27 ms 5888 KB Output is correct - 65266 call(s) of encode_bit()
9 Incorrect 31 ms 5820 KB Output isn't correct
10 Incorrect 26 ms 5760 KB wrong parameter
11 Incorrect 37 ms 6060 KB Output isn't correct
12 Incorrect 28 ms 5888 KB Output isn't correct
13 Incorrect 57 ms 6520 KB wrong parameter
14 Incorrect 31 ms 5956 KB Output isn't correct
15 Incorrect 36 ms 5900 KB Output isn't correct
16 Incorrect 51 ms 6476 KB wrong parameter
17 Incorrect 48 ms 6360 KB wrong parameter
18 Incorrect 62 ms 6720 KB wrong parameter
19 Incorrect 36 ms 6144 KB wrong parameter
20 Incorrect 67 ms 6944 KB wrong parameter
21 Incorrect 80 ms 7032 KB wrong parameter
22 Incorrect 89 ms 6580 KB wrong parameter
23 Incorrect 87 ms 7160 KB wrong parameter