Submission #565016

#	Time	Username	Problem	Language	Result	Execution time	Memory
565016		haxorman	Saveit (IOI10_saveit)	C++14	50 / 100	256 ms	12252 KiB

encoder

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

void encode(int n, int h, int m, int *v1, int *v2) {
	vector<int> graph[n + 1];
	for (int i = 0; i < m; ++i) {
		graph[v1[i]].push_back(v2[i]);
		graph[v2[i]].push_back(v1[i]);
	}

	for (int hub = 0; hub < h; ++hub) {
		vector<int> dist(n + 1, 1000000007);
		queue<int> q;

		q.push(hub);
		dist[hub] = 0;
		
		while (q.size()) {
			int u = q.front();
			q.pop();

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

		for (int u = 0; u < n; ++u) {
			for (int mask = 0; mask < 10; ++mask) {
				if (dist[u] & (1<<mask)) {
					encode_bit(1);
				}
				else {
					encode_bit(0);
				}
			}
		}
	}
  	return;
}

decoder

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

void decode(int n, int h) {
	for (int hub = 0; hub < h; ++hub) {
		for (int u = 0; u < n; ++u) {
			int dist = 0;
			for (int i = 0; i < 10; ++i) {
				int mask = decode_bit();
				if (mask) {
					dist += 1 << i;
				}
			}
			hops(hub, u, dist);
		}
	}
}

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