Submission #1225411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225411		boclobanchat	Saveit (IOI10_saveit)	C++20	100 / 100	50 ms	8776 KiB

encoder

#include"grader.h"
#include"encoder.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const int INF=1e9;
int dp[MAXN][MAXN],trace[MAXN],f[MAXN];
vector<int> ds[MAXN];
void encode(int nv,int nh,int ne,int *v1,int *v2)
{
	for(int i=0;i<ne;i++) ds[v1[i]].push_back(v2[i]),ds[v2[i]].push_back(v1[i]);
	for(int i=0;i<nh;i++)
	{
		queue<int> Q;
		for(int j=0;j<nv;j++) dp[i][j]=INF;
		dp[i][i]=0,Q.push(i);
		while(!Q.empty())
		{
			int a=Q.front();
			Q.pop();
			for(auto v:ds[a]) if(dp[i][v]==INF)
			{
				dp[i][v]=dp[i][a]+1,Q.push(v);
				if(!i) trace[v]=a;
			}
		}
	}
	for(int i=1;i<nv;i++) for(int j=9;j+1;j--) encode_bit((trace[i]>>j)%2);
	for(int i=0;i<nh;i++)
	{
		int v=0;
		for(int j=1;j<nv;j++)
		{
			f[j]=dp[i][j]-dp[i][trace[j]]+1,v=v*3+f[j];
			if(j%10==0||j==nv-1)
			{
				for(int k=15;k+1;k--) encode_bit((v>>k)%2);
				v=0;
			}
		}
	}
}

decoder

#include"grader.h"
#include"decoder.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1024;
const int INF=1e9;
int dp[MAXN][MAXN],F[MAXN][MAXN],trace[MAXN];
vector<int> ds[MAXN];
void dfs(int i,int pre,int c)
{
	if(i==pre) dp[c][i]=0;
	for(auto v:ds[i]) if(v!=pre)
	{
		dp[c][v]=dp[c][i]+F[i][v];
		dfs(v,i,c);
	}
}
void decode(int nv,int nh)
{
	for(int i=0;i<nv;i++) ds[i].clear();
	for(int i=1;i<nv;i++)
	{
		for(int j=9;j+1;j--) trace[i]=trace[i]*2+decode_bit();
		ds[i].push_back(trace[i]),ds[trace[i]].push_back(i);
	}
	for(int i=0;i<nh;i++)
	{
		int v=0;
		for(int j=1;j<nv;j++) if(j%10==0||j==nv-1)
		{
			for(int k=15;k+1;k--) v=v*2+decode_bit();
			for(int k=j;k>(j-1)/10*10;k--) F[trace[k]][k]=v%3-1,F[k][trace[k]]=-F[trace[k]][k],v/=3;
		}
		dfs(i,i,i);
		for(int j=0;j<nv;j++) hops(i,j,dp[i][j]);
	}
}

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