제출 #583410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583410		Jomnoi	Saveit (IOI10_saveit)	C++17	75 / 100	214 ms	13980 KiB

encoder

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

namespace {

const int MAX_N = 1005;

vector <int> graph[MAX_N];
int parent[MAX_N], dist[MAX_N];

}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    for(int i = 0; i < ne; i++) {
        graph[v1[i]].push_back(v2[i]);
        graph[v2[i]].push_back(v1[i]);
    }

    for(int i = 0; i < nv; i++) {
        dist[i] = -1;
    }
    
    queue <int> q;
    q.push(0);
    dist[0] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        for(auto v : graph[u]) {
            if(dist[v] == -1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }

    for(int i = 1; i < nv; i++) {
        for(int k = 0; k < 10; k++) {
            if((1<<k) & parent[i]) {
                encode_bit(1);
            }
            else {
                encode_bit(0);
            }
        }
    }

    for(int h = 1; h < nh; h++) {
        for(int i = 0; i < nv; i++) {
            dist[i] = -1;
        }

        queue <int> q;
        q.push(h);
        dist[h] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(auto v : graph[u]) {
                if(dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }

        for(int i = 1; i < nv; i++) {
            if(dist[i] == dist[parent[i]]) {
                encode_bit(0);
            }
            else {
                encode_bit(1);
                if(dist[i] < dist[parent[i]]) {
                    encode_bit(1);
                }
                else {
                    encode_bit(0);
                }
            }
        }
    }
}

decoder

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

namespace {

const int MAX_N = 1005;

vector <int> graph[MAX_N];
int parent[MAX_N];
int dist[MAX_N], W[MAX_N][MAX_N];

}

void decode(int nv, int nh) {
    for(int i = 1; i < nv; i++) {
        int p = 0;
        for(int k = 0; k < 10; k++) {
            p += (1<<k) * decode_bit();
        }

        parent[i] = p;
        graph[p].push_back(i);
        graph[i].push_back(p);
    }

    for(int i = 0; i < nv; i++) {
        dist[i] = -1;
    }

    queue <int> q;
    q.push(0);
    dist[0] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        for(auto v : graph[u]) {
            if(dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for(int i = 0; i < nv; i++) {
        hops(0, i, dist[i]);
    }

    for(int h = 1; h < nh; h++) {
        for(int i = 1; i < nv; i++) {
            if(decode_bit() == 0) {
                W[i][parent[i]] = 0;
                W[parent[i]][i] = 0;
            }
            else {
                if(decode_bit() == 1) {
                    W[i][parent[i]] = 1;
                    W[parent[i]][i] = -1;
                }
                else {
                    W[i][parent[i]] = -1;
                    W[parent[i]][i] = 1;
                }
            }
        }

        for(int i = 0; i < nv; i++) {
            dist[i] = -1;
        }

        queue <int> q;
        q.push(h);
        dist[h] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(auto v : graph[u]) {
                if(dist[v] == -1) {
                    dist[v] = dist[u] + W[u][v];
                    q.push(v);
                }
            }
        }

        for(int i = 0; i < nv; i++) {
            hops(h, i, dist[i]);
        }
    }
}

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