oj.uz

Submission #272126

# Submission time Handle Problem Language Result Execution time Memory
272126 2020-08-18T09:31:17 Z sjimed Saveit (IOI10_saveit) C++14
50 / 100
 260 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 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++) {
      if(ans[i][j] - ans[i][p[j]] == -1) encode_bit(0), encode_bit(0);
      else if(ans[i][j] - ans[i][p[j]] == 0) encode_bit(0), encode_bit(1);
      else encode_bit(1), encode_bit(0);

      /*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);
      }

      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 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++) {
         ans[i][j] = decode_bit() * 2 - 1;
         ans[i][j] += decode_bit();

         /*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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 11760 KB Output is partially correct - 82288 call(s) of encode_bit()
2 Correct 4 ms 4868 KB Output is correct - 104 call(s) of encode_bit()
3 Correct 28 ms 5888 KB Output is partially correct - 74088 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 40 ms 6144 KB Output is partially correct - 74088 call(s) of encode_bit()
6 Correct 41 ms 6144 KB Output is partially correct - 82288 call(s) of encode_bit()
7 Correct 89 ms 6548 KB Output is partially correct - 82288 call(s) of encode_bit()
8 Correct 36 ms 5960 KB Output is partially correct - 79090 call(s) of encode_bit()
9 Correct 39 ms 5888 KB Output is partially correct - 82288 call(s) of encode_bit()
10 Correct 32 ms 5880 KB Output is partially correct - 82288 call(s) of encode_bit()
11 Correct 43 ms 6256 KB Output is partially correct - 82288 call(s) of encode_bit()
12 Correct 32 ms 6064 KB Output is partially correct - 82288 call(s) of encode_bit()
13 Correct 61 ms 6656 KB Output is partially correct - 82288 call(s) of encode_bit()
14 Correct 35 ms 6024 KB Output is partially correct - 82288 call(s) of encode_bit()
15 Correct 35 ms 6000 KB Output is partially correct - 82288 call(s) of encode_bit()
16 Correct 79 ms 6736 KB Output is partially correct - 82288 call(s) of encode_bit()
17 Correct 62 ms 6400 KB Output is partially correct - 82288 call(s) of encode_bit()
18 Correct 96 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
19 Correct 56 ms 6392 KB Output is partially correct - 82288 call(s) of encode_bit()
20 Correct 130 ms 7316 KB Output is partially correct - 82288 call(s) of encode_bit()
21 Correct 145 ms 7032 KB Output is partially correct - 82288 call(s) of encode_bit()
22 Correct 56 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
23 Correct 79 ms 7320 KB Output is partially correct - 82288 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 11760 KB Output is partially correct - 82288 call(s) of encode_bit()
2 Correct 4 ms 4868 KB Output is correct - 104 call(s) of encode_bit()
3 Correct 28 ms 5888 KB Output is partially correct - 74088 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 40 ms 6144 KB Output is partially correct - 74088 call(s) of encode_bit()
6 Correct 41 ms 6144 KB Output is partially correct - 82288 call(s) of encode_bit()
7 Correct 89 ms 6548 KB Output is partially correct - 82288 call(s) of encode_bit()
8 Correct 36 ms 5960 KB Output is partially correct - 79090 call(s) of encode_bit()
9 Correct 39 ms 5888 KB Output is partially correct - 82288 call(s) of encode_bit()
10 Correct 32 ms 5880 KB Output is partially correct - 82288 call(s) of encode_bit()
11 Correct 43 ms 6256 KB Output is partially correct - 82288 call(s) of encode_bit()
12 Correct 32 ms 6064 KB Output is partially correct - 82288 call(s) of encode_bit()
13 Correct 61 ms 6656 KB Output is partially correct - 82288 call(s) of encode_bit()
14 Correct 35 ms 6024 KB Output is partially correct - 82288 call(s) of encode_bit()
15 Correct 35 ms 6000 KB Output is partially correct - 82288 call(s) of encode_bit()
16 Correct 79 ms 6736 KB Output is partially correct - 82288 call(s) of encode_bit()
17 Correct 62 ms 6400 KB Output is partially correct - 82288 call(s) of encode_bit()
18 Correct 96 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
19 Correct 56 ms 6392 KB Output is partially correct - 82288 call(s) of encode_bit()
20 Correct 130 ms 7316 KB Output is partially correct - 82288 call(s) of encode_bit()
21 Correct 145 ms 7032 KB Output is partially correct - 82288 call(s) of encode_bit()
22 Correct 56 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
23 Correct 79 ms 7320 KB Output is partially correct - 82288 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 11760 KB Output is partially correct - 82288 call(s) of encode_bit()
2 Correct 4 ms 4868 KB Output is correct - 104 call(s) of encode_bit()
3 Correct 28 ms 5888 KB Output is partially correct - 74088 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 40 ms 6144 KB Output is partially correct - 74088 call(s) of encode_bit()
6 Correct 41 ms 6144 KB Output is partially correct - 82288 call(s) of encode_bit()
7 Correct 89 ms 6548 KB Output is partially correct - 82288 call(s) of encode_bit()
8 Correct 36 ms 5960 KB Output is partially correct - 79090 call(s) of encode_bit()
9 Correct 39 ms 5888 KB Output is partially correct - 82288 call(s) of encode_bit()
10 Correct 32 ms 5880 KB Output is partially correct - 82288 call(s) of encode_bit()
11 Correct 43 ms 6256 KB Output is partially correct - 82288 call(s) of encode_bit()
12 Correct 32 ms 6064 KB Output is partially correct - 82288 call(s) of encode_bit()
13 Correct 61 ms 6656 KB Output is partially correct - 82288 call(s) of encode_bit()
14 Correct 35 ms 6024 KB Output is partially correct - 82288 call(s) of encode_bit()
15 Correct 35 ms 6000 KB Output is partially correct - 82288 call(s) of encode_bit()
16 Correct 79 ms 6736 KB Output is partially correct - 82288 call(s) of encode_bit()
17 Correct 62 ms 6400 KB Output is partially correct - 82288 call(s) of encode_bit()
18 Correct 96 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
19 Correct 56 ms 6392 KB Output is partially correct - 82288 call(s) of encode_bit()
20 Correct 130 ms 7316 KB Output is partially correct - 82288 call(s) of encode_bit()
21 Correct 145 ms 7032 KB Output is partially correct - 82288 call(s) of encode_bit()
22 Correct 56 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
23 Correct 79 ms 7320 KB Output is partially correct - 82288 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 11760 KB Output is partially correct - 82288 call(s) of encode_bit()
2 Correct 4 ms 4868 KB Output is correct - 104 call(s) of encode_bit()
3 Correct 28 ms 5888 KB Output is partially correct - 74088 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 140 call(s) of encode_bit()
5 Correct 40 ms 6144 KB Output is partially correct - 74088 call(s) of encode_bit()
6 Correct 41 ms 6144 KB Output is partially correct - 82288 call(s) of encode_bit()
7 Correct 89 ms 6548 KB Output is partially correct - 82288 call(s) of encode_bit()
8 Correct 36 ms 5960 KB Output is partially correct - 79090 call(s) of encode_bit()
9 Correct 39 ms 5888 KB Output is partially correct - 82288 call(s) of encode_bit()
10 Correct 32 ms 5880 KB Output is partially correct - 82288 call(s) of encode_bit()
11 Correct 43 ms 6256 KB Output is partially correct - 82288 call(s) of encode_bit()
12 Correct 32 ms 6064 KB Output is partially correct - 82288 call(s) of encode_bit()
13 Correct 61 ms 6656 KB Output is partially correct - 82288 call(s) of encode_bit()
14 Correct 35 ms 6024 KB Output is partially correct - 82288 call(s) of encode_bit()
15 Correct 35 ms 6000 KB Output is partially correct - 82288 call(s) of encode_bit()
16 Correct 79 ms 6736 KB Output is partially correct - 82288 call(s) of encode_bit()
17 Correct 62 ms 6400 KB Output is partially correct - 82288 call(s) of encode_bit()
18 Correct 96 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
19 Correct 56 ms 6392 KB Output is partially correct - 82288 call(s) of encode_bit()
20 Correct 130 ms 7316 KB Output is partially correct - 82288 call(s) of encode_bit()
21 Correct 145 ms 7032 KB Output is partially correct - 82288 call(s) of encode_bit()
22 Correct 56 ms 6648 KB Output is partially correct - 82288 call(s) of encode_bit()
23 Correct 79 ms 7320 KB Output is partially correct - 82288 call(s) of encode_bit()