Submission #1225008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225008		boclobanchat	Saveit (IOI10_saveit)	C++20	50 / 100	117 ms	7800 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];
bool ck[MAXN][MAXN];
vector<int> ds[MAXN],vi[MAXN];
bool comp(pair<int,long long> a,pair<int,long long> b)
{
	return __builtin_popcountll(a.second)>__builtin_popcountll(b.second);
}
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);
		}
	}
	for(int i=0;i<nv;i++)
	{
		vector< pair<int,long long> > vv;
		for(auto v:ds[i])
		{
			long long mask=0;
			for(int j=0;j<nh;j++) mask|=(1LL<<j)*(dp[j][i]==dp[j][v]+1);
			vv.push_back({v,mask});
		}
		sort(vv.begin(),vv.end(),comp);
		long long mask=0;
		for(auto v:vv)
		{
			if((mask&v.second)==v.second) continue;
			mask|=v.second;
			if(!ck[i][v.first]) ck[i][v.first]=ck[v.first][i]=true,vi[i].push_back(v.first);
			if(mask==(1LL<<(nh+1))-1) break;
		}
	}
	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