Submission #1252647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252647		PlayVoltz	Saveit (IOI10_saveit)	C++20	100 / 100	52 ms	8776 KiB

encoder

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

void encode(int n, int h, int e, int *u, int *v){
	vector<int> par(n);
	vector<vector<int> > graph(n), dj(h, vector<int>(n, -1));
	for (int i=0; i<e; ++i)graph[u[i]].pb(v[i]), graph[v[i]].pb(u[i]);
	for (int i=0; i<h; ++i){
		queue<int> q;
		dj[i][i]=0;
		q.push(i);
		while (q.size()){
			int node=q.front();
			q.pop();
			for (auto num:graph[node])if (dj[i][num]==-1){
				dj[i][num]=dj[i][node]+1;
				q.push(num);
				if (!i)par[num]=node;
			}
		}
	}
	for (int i=1; i<n; ++i)for (int j=0; j<10; ++j)encode_bit((par[i]>>j)&1);
	for (int i=0; i<h; ++i){
		int sum=0;
		for (int j=1; j<n; ++j){
			sum=sum*3+dj[i][j]-dj[i][par[j]]+1;
			if (!(j%10)||j==n-1){
				for (int b=0; b<16; ++b)encode_bit((sum>>b)&1);
				sum=0;
			}
		}
	}
}

decoder

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<vector<int> > graph, dist, diff;

void dfs(int node, int par, int t){
	if (par==-1)dist[t][node]=0;
	for (auto num:graph[node])if (num!=par)dist[t][num]=dist[t][node]+diff[node][num], dfs(num, node, t);
}

void decode(int n, int h){
  graph.clear();
  dist.clear();
  diff.clear();
	graph.resize(n);
	dist.resize(h, vector<int>(n));
	diff.resize(n, vector<int>(n, 0));
	vector<int> par(n, 0);
	for (int i=1; i<n; ++i){
		for (int j=0; j<10; ++j)par[i]+=decode_bit()*(1<<j);
		graph[i].pb(par[i]);
		graph[par[i]].pb(i);
	}
	for (int i=0; i<h; ++i){
		int sum=0;
		for (int j=1; j<n; ++j)if (!(j%10)||j==n-1){
			for (int b=0; b<16; ++b)sum+=decode_bit()*(1<<b);
			for (int p=j; p>(j-1)/10*10; --p)diff[par[p]][p]=sum%3-1, diff[p][par[p]]=1-sum%3, sum/=3;
		}
		dfs(i, -1, i);
		for (int j=0; j<n; ++j)hops(i, j, dist[i][j]);
	}
}

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