oj.uz

답안 #401887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401887 2021-05-11T00:09:28 Z ja_kingy 저장 (Saveit) (IOI10_saveit) C++14
75 / 100
 291 ms 10364 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int INF = 1e9;
static vector<int> g[1000];
static vector<pii> tr[1000];
static int dst[1000], vals[1000], seen[1000], ecnt;

template <int n>
void encode_num(int x) {
    bitset<n> bits(x);
    for (int i = 0; i < n; ++i) encode_bit(bits[i]);
}

void dfs_tr(int u) {
    seen[u] = 1;
    for (int v: g[u]) if (!seen[v]) {
        tr[u].push_back({v, ecnt});
        tr[v].push_back({u, ecnt});
        encode_num<10>(u);
        encode_num<10>(v);
        ecnt++;
        dfs_tr(v);
    }
}

void dfs(int u, int p) {
    for (pii e: tr[u]) if (e.first != p) {
        vals[e.second] = dst[e.first] - dst[u] + 1;
        dfs(e.first, u);
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    for (int i = 0; i < ne; ++i) {
        g[v1[i]].push_back(v2[i]);
        g[v2[i]].push_back(v1[i]);
    }
    dfs_tr(0);
    for (int i = 0; i < nh; ++i) {
        queue<int> bfs;
        fill(dst, end(dst), INF);
        bfs.push(i);
        dst[i] = 0;
        while (bfs.size()) {
            int u = bfs.front(); bfs.pop();
            for (int v: g[u]) {
                if (dst[u]+1 < dst[v]) {
                    dst[v] = dst[u]+1;
                    bfs.push(v);
                }
            }
        }
        dfs(i, -1);
        for (int j = 0; j < 1000; j += 5) {
            int v = 0;
            for (int k = 0; k < 5; ++k) {
                v*=3;
                v+=vals[j+k];
            }
            encode_num<8>(v);
        }
        /*for (int k = 0; k < nv; ++k) cerr << dst[k] << ' ';
        cerr << '\n';*/
    }
}

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

typedef pair<int,int> pii;
static vector<pii> tr[1000];
static int vals[1000];

void dfs(int u, int p, int d, int h) {
    hops(h, u, d);
    // cerr << h << ' ' << u << ' ' << d << endl;
    for (pii e: tr[u]) if (e.first != p) {
        dfs(e.first, u, d + vals[e.second], h);
    }
}

template <int n>
int decode_num() {
   bitset<n> bits;
   for (int i = 0; i < n; ++i) bits[i] = decode_bit();
   return bits.to_ulong();
}

void decode(int nv, int nh) {
   for (int i = 0; i < nv-1; ++i) {
      int a = decode_num<10>(), b = decode_num<10>();
      tr[a].push_back({b,i});
      tr[b].push_back({a,i});
   }
   for (int i = 0; i < nh; ++i) {
      for (int j = 0; j < 200; j++) {
          int v = decode_num<8>();
          for (int k = 0; k < 5; ++k) {
              vals[j*5+4-k] = (v%3)-1;
              v/=3;
          }
      }
      dfs(i, -1, 0, i);
   }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 10364 KB Output is partially correct - 77580 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 4880 call(s) of encode_bit()
3 Correct 28 ms 5596 KB Output is partially correct - 75580 call(s) of encode_bit()
4 Correct 5 ms 4580 KB Output is correct - 8080 call(s) of encode_bit()
5 Correct 34 ms 5648 KB Output is partially correct - 75580 call(s) of encode_bit()
6 Correct 34 ms 5752 KB Output is partially correct - 77580 call(s) of encode_bit()
7 Correct 53 ms 5996 KB Output is partially correct - 77580 call(s) of encode_bit()
8 Correct 31 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 33 ms 5472 KB Output is partially correct - 77580 call(s) of encode_bit()
10 Correct 31 ms 5456 KB Output is partially correct - 77580 call(s) of encode_bit()
11 Correct 33 ms 5732 KB Output is partially correct - 77580 call(s) of encode_bit()
12 Correct 28 ms 5584 KB Output is partially correct - 77580 call(s) of encode_bit()
13 Correct 57 ms 6132 KB Output is partially correct - 77580 call(s) of encode_bit()
14 Correct 37 ms 5648 KB Output is partially correct - 77580 call(s) of encode_bit()
15 Correct 32 ms 5688 KB Output is partially correct - 77580 call(s) of encode_bit()
16 Correct 62 ms 6172 KB Output is partially correct - 77580 call(s) of encode_bit()
17 Correct 62 ms 6048 KB Output is partially correct - 77580 call(s) of encode_bit()
18 Correct 67 ms 6348 KB Output is partially correct - 77580 call(s) of encode_bit()
19 Correct 42 ms 5968 KB Output is partially correct - 77580 call(s) of encode_bit()
20 Correct 78 ms 6588 KB Output is partially correct - 77580 call(s) of encode_bit()
21 Correct 109 ms 6680 KB Output is partially correct - 77580 call(s) of encode_bit()
22 Correct 80 ms 6168 KB Output is partially correct - 77580 call(s) of encode_bit()
23 Correct 89 ms 6940 KB Output is partially correct - 77580 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 10364 KB Output is partially correct - 77580 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 4880 call(s) of encode_bit()
3 Correct 28 ms 5596 KB Output is partially correct - 75580 call(s) of encode_bit()
4 Correct 5 ms 4580 KB Output is correct - 8080 call(s) of encode_bit()
5 Correct 34 ms 5648 KB Output is partially correct - 75580 call(s) of encode_bit()
6 Correct 34 ms 5752 KB Output is partially correct - 77580 call(s) of encode_bit()
7 Correct 53 ms 5996 KB Output is partially correct - 77580 call(s) of encode_bit()
8 Correct 31 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 33 ms 5472 KB Output is partially correct - 77580 call(s) of encode_bit()
10 Correct 31 ms 5456 KB Output is partially correct - 77580 call(s) of encode_bit()
11 Correct 33 ms 5732 KB Output is partially correct - 77580 call(s) of encode_bit()
12 Correct 28 ms 5584 KB Output is partially correct - 77580 call(s) of encode_bit()
13 Correct 57 ms 6132 KB Output is partially correct - 77580 call(s) of encode_bit()
14 Correct 37 ms 5648 KB Output is partially correct - 77580 call(s) of encode_bit()
15 Correct 32 ms 5688 KB Output is partially correct - 77580 call(s) of encode_bit()
16 Correct 62 ms 6172 KB Output is partially correct - 77580 call(s) of encode_bit()
17 Correct 62 ms 6048 KB Output is partially correct - 77580 call(s) of encode_bit()
18 Correct 67 ms 6348 KB Output is partially correct - 77580 call(s) of encode_bit()
19 Correct 42 ms 5968 KB Output is partially correct - 77580 call(s) of encode_bit()
20 Correct 78 ms 6588 KB Output is partially correct - 77580 call(s) of encode_bit()
21 Correct 109 ms 6680 KB Output is partially correct - 77580 call(s) of encode_bit()
22 Correct 80 ms 6168 KB Output is partially correct - 77580 call(s) of encode_bit()
23 Correct 89 ms 6940 KB Output is partially correct - 77580 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 10364 KB Output is partially correct - 77580 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 4880 call(s) of encode_bit()
3 Correct 28 ms 5596 KB Output is partially correct - 75580 call(s) of encode_bit()
4 Correct 5 ms 4580 KB Output is correct - 8080 call(s) of encode_bit()
5 Correct 34 ms 5648 KB Output is partially correct - 75580 call(s) of encode_bit()
6 Correct 34 ms 5752 KB Output is partially correct - 77580 call(s) of encode_bit()
7 Correct 53 ms 5996 KB Output is partially correct - 77580 call(s) of encode_bit()
8 Correct 31 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 33 ms 5472 KB Output is partially correct - 77580 call(s) of encode_bit()
10 Correct 31 ms 5456 KB Output is partially correct - 77580 call(s) of encode_bit()
11 Correct 33 ms 5732 KB Output is partially correct - 77580 call(s) of encode_bit()
12 Correct 28 ms 5584 KB Output is partially correct - 77580 call(s) of encode_bit()
13 Correct 57 ms 6132 KB Output is partially correct - 77580 call(s) of encode_bit()
14 Correct 37 ms 5648 KB Output is partially correct - 77580 call(s) of encode_bit()
15 Correct 32 ms 5688 KB Output is partially correct - 77580 call(s) of encode_bit()
16 Correct 62 ms 6172 KB Output is partially correct - 77580 call(s) of encode_bit()
17 Correct 62 ms 6048 KB Output is partially correct - 77580 call(s) of encode_bit()
18 Correct 67 ms 6348 KB Output is partially correct - 77580 call(s) of encode_bit()
19 Correct 42 ms 5968 KB Output is partially correct - 77580 call(s) of encode_bit()
20 Correct 78 ms 6588 KB Output is partially correct - 77580 call(s) of encode_bit()
21 Correct 109 ms 6680 KB Output is partially correct - 77580 call(s) of encode_bit()
22 Correct 80 ms 6168 KB Output is partially correct - 77580 call(s) of encode_bit()
23 Correct 89 ms 6940 KB Output is partially correct - 77580 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 10364 KB Output is partially correct - 77580 call(s) of encode_bit()
2 Correct 4 ms 4580 KB Output is correct - 4880 call(s) of encode_bit()
3 Correct 28 ms 5596 KB Output is partially correct - 75580 call(s) of encode_bit()
4 Correct 5 ms 4580 KB Output is correct - 8080 call(s) of encode_bit()
5 Correct 34 ms 5648 KB Output is partially correct - 75580 call(s) of encode_bit()
6 Correct 34 ms 5752 KB Output is partially correct - 77580 call(s) of encode_bit()
7 Correct 53 ms 5996 KB Output is partially correct - 77580 call(s) of encode_bit()
8 Correct 31 ms 5680 KB Output is partially correct - 76800 call(s) of encode_bit()
9 Correct 33 ms 5472 KB Output is partially correct - 77580 call(s) of encode_bit()
10 Correct 31 ms 5456 KB Output is partially correct - 77580 call(s) of encode_bit()
11 Correct 33 ms 5732 KB Output is partially correct - 77580 call(s) of encode_bit()
12 Correct 28 ms 5584 KB Output is partially correct - 77580 call(s) of encode_bit()
13 Correct 57 ms 6132 KB Output is partially correct - 77580 call(s) of encode_bit()
14 Correct 37 ms 5648 KB Output is partially correct - 77580 call(s) of encode_bit()
15 Correct 32 ms 5688 KB Output is partially correct - 77580 call(s) of encode_bit()
16 Correct 62 ms 6172 KB Output is partially correct - 77580 call(s) of encode_bit()
17 Correct 62 ms 6048 KB Output is partially correct - 77580 call(s) of encode_bit()
18 Correct 67 ms 6348 KB Output is partially correct - 77580 call(s) of encode_bit()
19 Correct 42 ms 5968 KB Output is partially correct - 77580 call(s) of encode_bit()
20 Correct 78 ms 6588 KB Output is partially correct - 77580 call(s) of encode_bit()
21 Correct 109 ms 6680 KB Output is partially correct - 77580 call(s) of encode_bit()
22 Correct 80 ms 6168 KB Output is partially correct - 77580 call(s) of encode_bit()
23 Correct 89 ms 6940 KB Output is partially correct - 77580 call(s) of encode_bit()