제출 #4680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4680		cki86201	Saveit (IOI10_saveit)	C++98	100 / 100	606 ms	13704 KiB

encoder

#include "grader.h"
#include "encoder.h"

void encode_number(int x,int u)
{
	for(int i=0;i<u;i++)encode_bit((x&(1<<i))!=0);
}

int st[1010],en[2000020],next[2000020];
bool check[1010];
int up[1010];

void addedge(int s,int d,int c){next[c]=st[s],st[s]=c,en[c]=d;}

void dfs(int x)
{
	check[x]=1;
	for(int i=st[x];i!=-1;i=next[i]){
		if(!check[en[i]]){
			up[en[i]]=x;
			dfs(en[i]);
		}
	}
}

int dis[40][1010],q[1010],now;

void bfs(int x)
{
    int *f,*r;
    f=r=q;
    *f++=x;
    check[x]=1;
    while(f!=r){
        int t=*r++;
        for(int i=st[t];i!=-1;i=next[i]){
            if(!check[en[i]])*f++=en[i],check[en[i]]=true,dis[now][en[i]]=dis[now][t]+1;
        }
    }
}

int v[100000],sz;

void encode(int nv, int nh, int ne, int *v1, int *v2){
	int i,j;
	for(i=0;i<nv;i++)st[i]=-1;
	for(i=0;i<ne;i++)addedge(v1[i],v2[i],i<<1),addedge(v2[i],v1[i],i<<1|1);
	dfs(0);
	for(i=1;i<nv;i++)encode_number(up[i],10);
	for(i=0;i<nh;i++){
		for(j=0;j<nv;j++)check[j]=0;
		now=i;
		bfs(i);
	}
	for(i=0;i<nh;i++){
		for(j=1;j<nv;j++){
			v[sz++] = dis[i][j] - dis[i][up[j]] + 1;
		}
	}
	for(i=0;i<sz;i+=5){
		int cnt=0,tmp=1;
		for(j=i;j<sz&&j<i+5;j++){
			cnt+=tmp*v[j];
			tmp*=3;
		}
		encode_number(cnt,8);
	}
	return;
}

decoder

#include "grader.h"
#include "decoder.h"

int pow3(int x){int t=1;for(int i=0;i<x;i++)t*=3;return t;}

int d_up[1010],nv;
int dec[100000];

inline int get_dist(int x,int y)
{
	return dec[(nv-1)*x+y-1];
}

bool chk[1010];
int dist[40][1010];

void solve(int x,int y)
{
	if(y==0)return;
	if(!chk[d_up[y]])solve(x,d_up[y]);
	dist[x][y]=dist[x][d_up[y]]+get_dist(x,y);
	chk[y]=1;
}

void decode(int nv, int nh){
	int i,j;
	::nv=nv;
	for(i=1;i<nv;i++)for(j=0;j<10;j++)d_up[i] += (1<<j)*decode_bit();
	for(i=0;i<((nv-1)*nh+4)/5;i++){
		int cnt=0;
		for(j=0;j<8;j++)cnt += (1<<j)*decode_bit();
		for(j=0;j<5;j++){
			dec[5*i+j]=(cnt%pow3(j+1))/pow3(j)-1;
		}
	}
	for(i=0;i<nh;i++){
		for(j=0;j<nv;j++)chk[j]=0;
		chk[0]=1;
		for(j=1;j<nv;j++)solve(i,j);
	}
	for(i=0;i<nh;i++)for(j=0;j<nv;j++)hops(i,j,dist[i][j]-dist[i][i]);
}

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