oj.uz

Submission #60863

# Submission time Handle Problem Language Result Execution time Memory
60863 2018-07-24T21:28:31 Z win11905 Saveit (IOI10_saveit) C++11
100 / 100
 390 ms 11656 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

static vector<int> g[N], ng[N];
static int d[N], par[N];
static bool chk[N];
static int ntsp[N];

void addShort(int u) {
  for(int i = 9; ~i; --i) encode_bit(u >> i & 1);
}

static void dfs(int u, int p) {
  if(u) par[u] = p, ng[u].emplace_back(p);
  chk[u] = true;
  for(int v : g[u]) if(v != p && !chk[v]) ng[u].emplace_back(v), dfs(v, u);
}

// 0 -1 1
void process(int u, int p) {
  ntsp[u] = (d[u] == d[p] ? 0 : (d[u] < d[p] ? 1 : 2));
  for(int v : ng[u]) if(v != p) process(v, u);
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  for(int i = 0; i < ne; ++i)
    g[v1[i]].emplace_back(v2[i]), g[v2[i]].emplace_back(v1[i]);
  dfs(0, -1);
  for(int i = 1; i < nv; ++i) addShort(par[i]);
  for(int i = 0; i < nh; ++i) {
    fill_n(d, N, (int)1e9);
    queue<int> Q; Q.emplace(i), d[i] = 0;
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      for(int v : g[u]) if(d[v] > d[u] + 1) 
        d[v] = d[u] + 1, Q.emplace(v);
    }
    process(i, i);
    for(int i = 0; i < 200; ++i) {
      int sum = 0;
      for(int j = 4; ~j; --j) sum = sum * 3 + ntsp[5*i+j];
      for(int j = 7; ~j; --j) encode_bit(sum >> j & 1);
    }
  } 
  return;
}

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

const int N = 1e3+5;

static vector<int> g[N];
static int d[N], v[N], z[N];

int getInt(int len) {
    int sum = 0;
    for(int i = 0; i < len; ++i) sum = (sum<<1) + decode_bit();
    return sum;
}

static void dfs(int u, int p) {
    d[u] = d[p] + v[u];
    for(int v : g[u]) if(v != p) dfs(v, u);
}

void decode(int nv, int nh) {
    for(int i = 1; i < nv; ++i) {
        int p = getInt(10);
        g[p].emplace_back(i), g[i].emplace_back(p);
    }
    for(int i = 0; i < nh; ++i) {
        d[i] = 0;
        for(int j = 0; j < 200; ++j) {
            int ret = getInt(8);
            for(int k = 0; k < 5; ++k) z[j*5+k] = ret % 3, ret /= 3;
        }
        for(int j = 0; j < 1000; ++j) v[j] = (z[j] == 0 ? 0 : (z[j] == 1 ? -1 : 1));
        dfs(i, i);
        for(int j = 0; j < nv; ++j) hops(i, j, d[j]);
    }
    return;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 11656 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 8 ms 4796 KB Output is correct - 4840 call(s) of encode_bit()
3 Correct 30 ms 5692 KB Output is correct - 66590 call(s) of encode_bit()
4 Correct 9 ms 4824 KB Output is correct - 8040 call(s) of encode_bit()
5 Correct 36 ms 5772 KB Output is correct - 66590 call(s) of encode_bit()
6 Correct 41 ms 5856 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 53 ms 6204 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 30 ms 5576 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 33 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 27 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 45 ms 5712 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 32 ms 5736 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 84 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 44 ms 5708 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 35 ms 5872 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 47 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 55 ms 6196 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 104 ms 6408 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 60 ms 5920 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 70 ms 6784 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 98 ms 6768 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 83 ms 6308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 119 ms 6976 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 11656 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 8 ms 4796 KB Output is correct - 4840 call(s) of encode_bit()
3 Correct 30 ms 5692 KB Output is correct - 66590 call(s) of encode_bit()
4 Correct 9 ms 4824 KB Output is correct - 8040 call(s) of encode_bit()
5 Correct 36 ms 5772 KB Output is correct - 66590 call(s) of encode_bit()
6 Correct 41 ms 5856 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 53 ms 6204 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 30 ms 5576 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 33 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 27 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 45 ms 5712 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 32 ms 5736 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 84 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 44 ms 5708 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 35 ms 5872 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 47 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 55 ms 6196 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 104 ms 6408 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 60 ms 5920 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 70 ms 6784 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 98 ms 6768 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 83 ms 6308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 119 ms 6976 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 11656 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 8 ms 4796 KB Output is correct - 4840 call(s) of encode_bit()
3 Correct 30 ms 5692 KB Output is correct - 66590 call(s) of encode_bit()
4 Correct 9 ms 4824 KB Output is correct - 8040 call(s) of encode_bit()
5 Correct 36 ms 5772 KB Output is correct - 66590 call(s) of encode_bit()
6 Correct 41 ms 5856 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 53 ms 6204 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 30 ms 5576 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 33 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 27 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 45 ms 5712 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 32 ms 5736 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 84 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 44 ms 5708 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 35 ms 5872 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 47 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 55 ms 6196 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 104 ms 6408 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 60 ms 5920 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 70 ms 6784 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 98 ms 6768 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 83 ms 6308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 119 ms 6976 KB Output is correct - 67590 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 11656 KB Output is correct - 67590 call(s) of encode_bit()
2 Correct 8 ms 4796 KB Output is correct - 4840 call(s) of encode_bit()
3 Correct 30 ms 5692 KB Output is correct - 66590 call(s) of encode_bit()
4 Correct 9 ms 4824 KB Output is correct - 8040 call(s) of encode_bit()
5 Correct 36 ms 5772 KB Output is correct - 66590 call(s) of encode_bit()
6 Correct 41 ms 5856 KB Output is correct - 67590 call(s) of encode_bit()
7 Correct 53 ms 6204 KB Output is correct - 67590 call(s) of encode_bit()
8 Correct 30 ms 5576 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 33 ms 5740 KB Output is correct - 67590 call(s) of encode_bit()
10 Correct 27 ms 5616 KB Output is correct - 67590 call(s) of encode_bit()
11 Correct 45 ms 5712 KB Output is correct - 67590 call(s) of encode_bit()
12 Correct 32 ms 5736 KB Output is correct - 67590 call(s) of encode_bit()
13 Correct 84 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
14 Correct 44 ms 5708 KB Output is correct - 67590 call(s) of encode_bit()
15 Correct 35 ms 5872 KB Output is correct - 67590 call(s) of encode_bit()
16 Correct 47 ms 6368 KB Output is correct - 67590 call(s) of encode_bit()
17 Correct 55 ms 6196 KB Output is correct - 67590 call(s) of encode_bit()
18 Correct 104 ms 6408 KB Output is correct - 67590 call(s) of encode_bit()
19 Correct 60 ms 5920 KB Output is correct - 67590 call(s) of encode_bit()
20 Correct 70 ms 6784 KB Output is correct - 67590 call(s) of encode_bit()
21 Correct 98 ms 6768 KB Output is correct - 67590 call(s) of encode_bit()
22 Correct 83 ms 6308 KB Output is correct - 67590 call(s) of encode_bit()
23 Correct 119 ms 6976 KB Output is correct - 67590 call(s) of encode_bit()