제출 #512377

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512377		alextodoran	저장 (Saveit) (IOI10_saveit)	C++17	0 / 100	289 ms	10516 KiB

encoder

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
 
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N_MAX = 1000;
const int H_MAX = 36;
 
int N, H, E;
 
int dist[H_MAX][N_MAX];
 
int parent[N_MAX];
 
#include "grader.h"
#include "encoder.h"
 
void encode_bit (int bit);
 
void encode_int (int val, int len) {
    for (int bit = len - 1; bit >= 0; bit--) {
        encode_bit((val >> bit) & 1);
    }
}
 
vector <int> adj[N_MAX];
 
void dfs (int u) {
    for (int v : adj[u]) {
        if (parent[v] == -1) {
            parent[v] = u;
            dfs(v);
        }
    }
}
void dfs () {
    for (int u = 0; u < N; u++) {
        parent[u] = -1;
    }
    parent[0] = N;
    dfs(0);
}
 
void bfs (int s, int dist[]) {
    for (int u = 0; u < N; u++) {
        dist[u] = -1;
    }
    queue <int> q;
    dist[s] = 0;
    q.push(s);
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}
 
void encode (int nv, int nh, int ne, int *v1, int *v2) {
    N = nv; H = nh; E = ne;
    for (int i = 0; i < E; i++) {
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }
    dfs();
    for (int u = 1; u < N; u++) {
        encode_int(parent[u], 10);
    }
    for (int h = 0; h < H; h++) {
        bfs(h, dist[h]);
        encode_int(dist[h][0], 10);
        for (int u = 1; u < N; u++) {
            encode_int(1 + (dist[h][u] - dist[h][parent[u]]), 2);
        }
    }
}

decoder

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
 
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N_MAX = 1000;
const int H_MAX = 36;
 
int N, H, E;
 
int dist[H_MAX][N_MAX];
 
int parent[N_MAX];
 
#include "grader.h"
#include "decoder.h"
 
int decode_bit ();
 
void hops (int a, int b, int d);
 
int decode_int (int len) {
    int val = 0;
    for (int bit = len - 1; bit >= 0; bit--) {
        val |= (decode_bit() << bit);
    }
    return val;
}
 
void decode (int nv, int nh) {
    N = nv; H = nh;
    for (int u = 1; u < N; u++) {
        parent[u] = decode_int(10);
    }
    for (int h = 0; h < H; h++) {
        dist[h][0] = decode_int(10);
        for (int u = 1; u < N; u++) {
            dist[h][u] = dist[h][parent[u]] + (decode_int(2) - 1);
        }
    }
    for (int h = 0; h < H; h++) {
        for (int u = 0; u < N; u++) {
            hops(h, u, dist[h][u]);
        }
    }
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25