Submission #362642

#	Time	Username	Problem	Language	Result	Execution time	Memory
362642		LucaDantas	Saveit (IOI10_saveit)	C++17	100 / 100	289 ms	10844 KiB

encoder

#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

#define pb push_back

constexpr int maxn = 1e3+10;

static int pai[maxn], dist[maxn];

static vector<int> g[maxn];

bool on(int a, int b) {return a&(1<<b);}

void dfs(int u) {
	dist[u] = 1;
	for(int v : g[u])
		if(!dist[v])
			pai[v] = u, dfs(v);
}

void encode(int N, int H, int M, int *A, int *B){
	for(int i = 0; i < M; i++)
		g[A[i]].pb(B[i]), g[B[i]].pb(A[i]);
	memset(pai, -1, sizeof pai);
	dfs(0);
	for(int i = 1; i < N; i++)
		for(int j = 0; j < 10; j++)
			encode_bit(on(pai[i], j));
	for(int i = 0; i < H; i++) {
		queue<int> q;
		for(int j = 0; j < N; j++)
			dist[j] = maxn;
		q.push(i);
		dist[i] = 0;

		while(q.size()) {
			int u = q.front(); q.pop();
			for(int v : g[u])
				if(dist[v] > dist[u]+1)
					q.push(v), dist[v] = dist[u]+1;
		}

		for(int j = 1; j < N; j += 3) {
			int pot[3] = {1, 3, 9}, p = 0;
			for(int k : {0, 1, 2})
				p += (dist[pai[j+k]]-dist[j+k]+1)*pot[k];
			for(int k = 0; k < 5; k++)
				encode_bit(on(p, k));
		}
	}
}

decoder

#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using namespace std;

#define pb push_back

constexpr int maxn = 1e3+10;

static int pai[maxn], dist[maxn], f[maxn];

static vector<int> g[maxn];

bool mark[maxn];

void dfs_ans(int u) {
	mark[u] = 1;
	if(!mark[pai[u]])
		dist[pai[u]] = dist[u] + f[u], dfs_ans(pai[u]);
	for(int v : g[u]) {
		if(mark[v]) continue;
		dist[v] = dist[u] - f[v];
		dfs_ans(v);
	}
}

void decode(int N, int H) {
	for(int i = 1; i < N; i++) {
		for(int j = 0; j < 10; j++)
			pai[i] += decode_bit()<<j;
		g[pai[i]].pb(i);
	}
	for(int i = 0; i < H; i++) {
		for(int j = 1; j < N; j += 3) {
			int p = 0;
			for(int k = 0; k < 5; k++)
				p += decode_bit()<<k;
			int pot[] = {1, 3, 9, 27};
			for(int k : {0, 1, 2})
				f[j+k] = ((p%pot[k+1])/pot[k])-1;
		}
		dfs_ans(i);
		for(int j = 0; j < N; j++)
			hops(i, j, dist[j]);
		memset(f, 0, sizeof f);
		memset(dist, 0, sizeof dist);
		memset(mark, 0, sizeof mark);
	}
}

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