Submission #1019089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019089		socpite	Saveit (IOI10_saveit)	C++14	50 / 100	325 ms	15008 KiB

encoder

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

namespace {

const int maxn = 1e3+5;

int E[maxn][maxn];
int dist[maxn][maxn];
int vis[maxn];
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
	memset(E, 0, sizeof(E));
	memset(dist, 0, sizeof(dist));
	memset(vis, 0, sizeof(vis));
	for(int i = 0; i < ne; i++)E[v1[i]][v2[i]] = E[v2[i]][v1[i]] = 1;
	for(int i = 0; i < nh; i++){
		dist[i][i] = 0;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			auto x = q.front();
			q.pop();
			for(int j = 0; j < nv; j++){
				if(!E[x][j] || dist[i][j] || j == i)continue;
				dist[i][j] = dist[i][x] + 1;
				q.push(j);
			}
		}
	}
	mt19937 rng(69420);
	vector<int> vec(nh);
	iota(vec.begin(), vec.end(), 0);
	shuffle(vec.begin(), vec.end(), rng);
	for(int i = 0; i < nh; i++){
		vis[vec[i]] = 1;
		for(int j = 0; j < nv; j++){
			if(vis[j])continue;
			int mx = nv-1;
			for(int k = 0; k < i; k++){
				mx = min(mx, dist[vec[k]][vec[i]] + dist[vec[k]][j]);
			}
			mx--;
			int tmp = dist[vec[i]][j]-1;
			while(mx){
				encode_bit(tmp&1);
				tmp>>=1;
				mx>>=1;
			}
		}
	}
}

decoder

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

namespace {

const int maxn = 1e3+5;

int dist[maxn][maxn];
int vis[maxn];

}

void decode(int nv, int nh) {
	memset(vis, 0, sizeof(vis));
   	mt19937 rng(69420);
	vector<int> vec(nh);
	iota(vec.begin(), vec.end(), 0);
	shuffle(vec.begin(), vec.end(), rng);
	for(int i = 0; i < nh; i++){
		vis[vec[i]] = 1;
		for(int j = 0; j < nv; j++){
			if(vis[j]){
				hops(vec[i], j, dist[j][vec[i]]);
				continue;
			}
			int mx = nv-1;
			for(int k = 0; k < i; k++){
				mx = min(mx, dist[vec[k]][vec[i]] + dist[vec[k]][j]);
			}
			mx--;
			dist[vec[i]][j] = 0;
			int crr = 0;
			while(mx){
				dist[vec[i]][j]|=decode_bit()<<(crr++);
				mx>>=1;
			}
			dist[vec[i]][j]++;
			hops(vec[i], j, dist[vec[i]][j]);
		}
	}
}

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