Submission #1224858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224858		boclobanchat	Saveit (IOI10_saveit)	C++20	50 / 100	146 ms	6956 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][MAXN];
vector<int> ds[MAXN],vi[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,trace[i][v]=a,Q.push(v);
		}
		for(int j=0;j<nv;j++) if(j!=i)
		{
			for(auto v:ds[j]) if(dp[i][j]==dp[i][v]+1)
			{
				bool ck=false;
				for(int l=0;l<i;l++) ck|=(l==v);
				if(ck)
				{
					trace[i][j]=v;
					break;
				}
			}
			vi[j].push_back(trace[i][j]);
		}
	}
	for(int i=0;i<nv;i++)
	{
		sort(vi[i].begin(),vi[i].end());
		vi[i].erase(unique(vi[i].begin(),vi[i].end()),vi[i].end());
		int sz=vi[i].size();
		for(int j=5;j+1;j--) encode_bit((sz>>j)%2);
		for(auto v:vi[i]) for(int j=9;j+1;j--) encode_bit((v>>j)%2);
	}
}

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],trace[MAXN][MAXN];
vector<int> ds[MAXN],vi[MAXN];
void decode(int nv,int nh)
{
	for(int i=0;i<nv;i++)
	{
		int sz=0;
		for(int j=5;j+1;j--) sz=sz*2+decode_bit();
		while(sz--)
		{
			int res=0;
			for(int j=9;j+1;j--) res=res*2+decode_bit();
			ds[i].push_back(res),ds[res].push_back(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,trace[i][v]=a,Q.push(v);
		}
		for(int j=0;j<nv;j++) hops(i,j,dp[i][j]);
	}
}

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