oj.uz

Submission #4680

# Submission time Handle Problem Language Result Execution time Memory
4680 2013-12-11T00:10:39 Z cki86201 Saveit (IOI10_saveit) C++
100 / 100
 606 ms 13704 KB 
#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;
}

#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 13704 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 5 ms 4716 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5984 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4712 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6084 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 45 ms 6192 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 63 ms 6728 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5972 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 31 ms 6004 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 34 ms 6028 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 39 ms 6196 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 26 ms 6080 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 101 ms 6960 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 5996 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 43 ms 6228 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 73 ms 6800 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 78 ms 6528 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 90 ms 7004 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 60 ms 6440 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 109 ms 7128 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 127 ms 7492 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 102 ms 6720 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 119 ms 7636 KB Output is correct - 67534 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 13704 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 5 ms 4716 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5984 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4712 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6084 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 45 ms 6192 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 63 ms 6728 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5972 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 31 ms 6004 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 34 ms 6028 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 39 ms 6196 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 26 ms 6080 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 101 ms 6960 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 5996 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 43 ms 6228 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 73 ms 6800 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 78 ms 6528 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 90 ms 7004 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 60 ms 6440 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 109 ms 7128 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 127 ms 7492 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 102 ms 6720 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 119 ms 7636 KB Output is correct - 67534 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 13704 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 5 ms 4716 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5984 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4712 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6084 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 45 ms 6192 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 63 ms 6728 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5972 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 31 ms 6004 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 34 ms 6028 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 39 ms 6196 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 26 ms 6080 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 101 ms 6960 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 5996 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 43 ms 6228 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 73 ms 6800 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 78 ms 6528 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 90 ms 7004 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 60 ms 6440 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 109 ms 7128 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 127 ms 7492 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 102 ms 6720 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 119 ms 7636 KB Output is correct - 67534 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 13704 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 5 ms 4716 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 27 ms 5984 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4712 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6084 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 45 ms 6192 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 63 ms 6728 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5972 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 31 ms 6004 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 34 ms 6028 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 39 ms 6196 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 26 ms 6080 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 101 ms 6960 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 5996 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 43 ms 6228 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 73 ms 6800 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 78 ms 6528 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 90 ms 7004 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 60 ms 6440 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 109 ms 7128 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 127 ms 7492 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 102 ms 6720 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 119 ms 7636 KB Output is correct - 67534 call(s) of encode_bit()