oj.uz

Submission #74084

# Submission time Handle Problem Language Result Execution time Memory
74084 2018-08-30T04:19:00 Z ainta Saveit (IOI10_saveit) C++17
100 / 100
 520 ms 14136 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 520 ms 14136 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 11 ms 4672 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 28 ms 5908 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6076 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 43 ms 6180 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 102 ms 6640 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5948 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 26 ms 5988 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 30 ms 5952 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 54 ms 6308 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 28 ms 5900 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 86 ms 6804 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 33 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 90 ms 6716 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 72 ms 6648 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 85 ms 6904 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 55 ms 6492 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 121 ms 7232 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 129 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 101 ms 6844 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 202 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 14136 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 11 ms 4672 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 28 ms 5908 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6076 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 43 ms 6180 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 102 ms 6640 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5948 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 26 ms 5988 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 30 ms 5952 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 54 ms 6308 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 28 ms 5900 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 86 ms 6804 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 33 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 90 ms 6716 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 72 ms 6648 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 85 ms 6904 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 55 ms 6492 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 121 ms 7232 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 129 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 101 ms 6844 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 202 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 14136 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 11 ms 4672 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 28 ms 5908 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6076 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 43 ms 6180 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 102 ms 6640 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5948 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 26 ms 5988 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 30 ms 5952 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 54 ms 6308 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 28 ms 5900 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 86 ms 6804 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 33 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 90 ms 6716 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 72 ms 6648 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 85 ms 6904 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 55 ms 6492 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 121 ms 7232 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 129 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 101 ms 6844 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 202 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 14136 KB Output is correct - 67534 call(s) of encode_bit()
2 Correct 11 ms 4672 KB Output is correct - 64 call(s) of encode_bit()
3 Correct 28 ms 5908 KB Output is correct - 60774 call(s) of encode_bit()
4 Correct 7 ms 4796 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 38 ms 6076 KB Output is correct - 60774 call(s) of encode_bit()
6 Correct 43 ms 6180 KB Output is correct - 67534 call(s) of encode_bit()
7 Correct 102 ms 6640 KB Output is correct - 67534 call(s) of encode_bit()
8 Correct 28 ms 5948 KB Output is correct - 64896 call(s) of encode_bit()
9 Correct 26 ms 5988 KB Output is correct - 67534 call(s) of encode_bit()
10 Correct 30 ms 5952 KB Output is correct - 67534 call(s) of encode_bit()
11 Correct 54 ms 6308 KB Output is correct - 67534 call(s) of encode_bit()
12 Correct 28 ms 5900 KB Output is correct - 67534 call(s) of encode_bit()
13 Correct 86 ms 6804 KB Output is correct - 67534 call(s) of encode_bit()
14 Correct 32 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
15 Correct 33 ms 6076 KB Output is correct - 67534 call(s) of encode_bit()
16 Correct 90 ms 6716 KB Output is correct - 67534 call(s) of encode_bit()
17 Correct 72 ms 6648 KB Output is correct - 67534 call(s) of encode_bit()
18 Correct 85 ms 6904 KB Output is correct - 67534 call(s) of encode_bit()
19 Correct 55 ms 6492 KB Output is correct - 67534 call(s) of encode_bit()
20 Correct 121 ms 7232 KB Output is correct - 67534 call(s) of encode_bit()
21 Correct 129 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()
22 Correct 101 ms 6844 KB Output is correct - 67534 call(s) of encode_bit()
23 Correct 202 ms 7464 KB Output is correct - 67534 call(s) of encode_bit()