Submission #405196

#	Time	Username	Problem	Language	Result	Execution time	Memory
405196		Jasiekstrz	저장 (Saveit) (IOI10_saveit)	C++17	100 / 100	342 ms	10376 KiB

encoder

#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
const int N=1e3,H=36;
vector<int> e[N+10];
int d[H+2][N+10];
bool vis[N+10];
void send_int(int x)
{
	for(int i=9;i>=0;i--)
		encode_bit((x&(1<<i))!=0);
	return;
}
void bfs(int n,int x)
{
	for(int i=0;i<n;i++)
		vis[i]=false;
	queue<int> qq;
	qq.push(x);
	vis[x]=true;
	d[x][x]=0;
	while(!qq.empty())
	{
		int y=qq.front();
		qq.pop();
		//cerr<<"d "<<x<<" "<<y<<" "<<d[x][y]<<"\n";
		for(auto v:e[y])
		{
			//cerr<<"e "<<x<<" "<<v<<"\n";
			if(!vis[v])
			{
				vis[v]=true;
				qq.push(v);
				d[x][v]=d[x][y]+1;
			}
		}
	}
	return;
}
void send_weight(int x,int y,int h)
{
	long long tmp=0;
	for(int i=h-1;i>=0;i--)
		tmp=3*tmp+1+d[i][y]-d[i][x];
	//cerr<<x<<" "<<y<<" "<<tmp<<"\n";
	for(int i=57;i>=0;i--)
		encode_bit((tmp&(1LL<<i))!=0);
	return;
}
void dfs(int x,int h)
{
	//cerr<<"dfs_en "<<x<<"\n";
	vis[x]=true;
	for(auto v:e[x])
	{
		if(vis[v])
			continue;
		encode_bit(0);
		send_int(v);
		send_weight(x,v,h);
		dfs(v,h);
	}
	encode_bit(1);
	return;
}
void encode(int nv,int nh,int ne,int *v1,int *v2)
{
	for(int i=0;i<ne;i++)
	{
		e[v1[i]].push_back(v2[i]);
		e[v2[i]].push_back(v1[i]);
	}
	for(int i=0;i<nh;i++)
		bfs(nv,i);
	for(int i=0;i<nv;i++)
		vis[i]=false;
	dfs(0,nh);
	encode_bit(1);
	return;
}

decoder

#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
#define fi first
#define se second
using namespace std;
static const int N=1e3;
static vector<pair<int,long long>> e[N+10];
int receive_int()
{
	int ans=0;
	for(int i=0;i<10;i++)
		ans=(2*ans+decode_bit());
	return ans;
}
long long receive_weight()
{
	long long ans=0;
	for(int i=0;i<58;i++)
		ans=(2*ans+decode_bit());
	return ans;
}
long long reverse_weight(long long w,int h)
{
	long long tmp=0;
	for(int i=0;i<h;i++,w/=3)
		tmp=3*tmp+2-w%3;
	for(int i=0;i<h;i++,tmp/=3)
		w=3*w+tmp%3;
	return w;
}
static void dfs(int x,int h)
{
	while(!decode_bit())
	{
		int y=receive_int();
		long long w=receive_weight();
		//cerr<<x<<" "<<y<<" "<<w<<"\n";
		e[x].emplace_back(y,w);
		e[y].emplace_back(x,reverse_weight(w,h));
		dfs(y,h);
	}
	return;
}
static void dfs_ans(int x,int p,int h,int dd)
{
	//cerr<<h<<" "<<x<<" "<<dd<<"\n";
	hops(h,x,dd);
	//cerr<<"ok\n";
	for(auto &v:e[x])
	{
		//cerr<<x<<"("<<p<<")"<<" "<<v.fi<<" "<<v.se<<"\n";
		if(v.fi!=p)
		{
			//cerr<<"ok\n";
			dfs_ans(v.fi,x,h,dd+v.se%3-1);
			//cerr<<"ok2\n";
		}
		v.se/=3;
	}
	return;
}
void decode(int nv,int nh)
{
	dfs(0,nh);
	for(int i=0;i<nh;i++)
		dfs_ans(i,-1,i,0);
	return;
}

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