oj.uz

Submission #405196

# Submission time Handle Problem Language Result Execution time Memory
405196 2021-05-15T20:53:08 Z Jasiekstrz Saveit (IOI10_saveit) C++17
100 / 100
 342 ms 10376 KB 
#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;
}

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

# Verdict Execution time Memory Grader output
1 Correct 342 ms 10376 KB Output is correct - 69932 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
3 Correct 24 ms 5608 KB Output is correct - 62932 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
5 Correct 30 ms 5756 KB Output is correct - 62932 call(s) of encode_bit()
6 Correct 28 ms 5788 KB Output is correct - 69932 call(s) of encode_bit()
7 Correct 48 ms 6032 KB Output is correct - 69932 call(s) of encode_bit()
8 Correct 26 ms 5548 KB Output is correct - 67202 call(s) of encode_bit()
9 Correct 27 ms 5596 KB Output is correct - 69932 call(s) of encode_bit()
10 Correct 28 ms 5604 KB Output is correct - 69932 call(s) of encode_bit()
11 Correct 32 ms 5748 KB Output is correct - 69932 call(s) of encode_bit()
12 Correct 27 ms 5712 KB Output is correct - 69932 call(s) of encode_bit()
13 Correct 56 ms 6304 KB Output is correct - 69932 call(s) of encode_bit()
14 Correct 28 ms 5692 KB Output is correct - 69932 call(s) of encode_bit()
15 Correct 28 ms 5716 KB Output is correct - 69932 call(s) of encode_bit()
16 Correct 54 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
17 Correct 46 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
18 Correct 72 ms 6392 KB Output is correct - 69932 call(s) of encode_bit()
19 Correct 46 ms 5956 KB Output is correct - 69932 call(s) of encode_bit()
20 Correct 60 ms 6684 KB Output is correct - 69932 call(s) of encode_bit()
21 Correct 94 ms 6860 KB Output is correct - 69932 call(s) of encode_bit()
22 Correct 63 ms 6224 KB Output is correct - 69932 call(s) of encode_bit()
23 Correct 106 ms 7000 KB Output is correct - 69932 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 10376 KB Output is correct - 69932 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
3 Correct 24 ms 5608 KB Output is correct - 62932 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
5 Correct 30 ms 5756 KB Output is correct - 62932 call(s) of encode_bit()
6 Correct 28 ms 5788 KB Output is correct - 69932 call(s) of encode_bit()
7 Correct 48 ms 6032 KB Output is correct - 69932 call(s) of encode_bit()
8 Correct 26 ms 5548 KB Output is correct - 67202 call(s) of encode_bit()
9 Correct 27 ms 5596 KB Output is correct - 69932 call(s) of encode_bit()
10 Correct 28 ms 5604 KB Output is correct - 69932 call(s) of encode_bit()
11 Correct 32 ms 5748 KB Output is correct - 69932 call(s) of encode_bit()
12 Correct 27 ms 5712 KB Output is correct - 69932 call(s) of encode_bit()
13 Correct 56 ms 6304 KB Output is correct - 69932 call(s) of encode_bit()
14 Correct 28 ms 5692 KB Output is correct - 69932 call(s) of encode_bit()
15 Correct 28 ms 5716 KB Output is correct - 69932 call(s) of encode_bit()
16 Correct 54 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
17 Correct 46 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
18 Correct 72 ms 6392 KB Output is correct - 69932 call(s) of encode_bit()
19 Correct 46 ms 5956 KB Output is correct - 69932 call(s) of encode_bit()
20 Correct 60 ms 6684 KB Output is correct - 69932 call(s) of encode_bit()
21 Correct 94 ms 6860 KB Output is correct - 69932 call(s) of encode_bit()
22 Correct 63 ms 6224 KB Output is correct - 69932 call(s) of encode_bit()
23 Correct 106 ms 7000 KB Output is correct - 69932 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 10376 KB Output is correct - 69932 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
3 Correct 24 ms 5608 KB Output is correct - 62932 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
5 Correct 30 ms 5756 KB Output is correct - 62932 call(s) of encode_bit()
6 Correct 28 ms 5788 KB Output is correct - 69932 call(s) of encode_bit()
7 Correct 48 ms 6032 KB Output is correct - 69932 call(s) of encode_bit()
8 Correct 26 ms 5548 KB Output is correct - 67202 call(s) of encode_bit()
9 Correct 27 ms 5596 KB Output is correct - 69932 call(s) of encode_bit()
10 Correct 28 ms 5604 KB Output is correct - 69932 call(s) of encode_bit()
11 Correct 32 ms 5748 KB Output is correct - 69932 call(s) of encode_bit()
12 Correct 27 ms 5712 KB Output is correct - 69932 call(s) of encode_bit()
13 Correct 56 ms 6304 KB Output is correct - 69932 call(s) of encode_bit()
14 Correct 28 ms 5692 KB Output is correct - 69932 call(s) of encode_bit()
15 Correct 28 ms 5716 KB Output is correct - 69932 call(s) of encode_bit()
16 Correct 54 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
17 Correct 46 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
18 Correct 72 ms 6392 KB Output is correct - 69932 call(s) of encode_bit()
19 Correct 46 ms 5956 KB Output is correct - 69932 call(s) of encode_bit()
20 Correct 60 ms 6684 KB Output is correct - 69932 call(s) of encode_bit()
21 Correct 94 ms 6860 KB Output is correct - 69932 call(s) of encode_bit()
22 Correct 63 ms 6224 KB Output is correct - 69932 call(s) of encode_bit()
23 Correct 106 ms 7000 KB Output is correct - 69932 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 10376 KB Output is correct - 69932 call(s) of encode_bit()
2 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
3 Correct 24 ms 5608 KB Output is correct - 62932 call(s) of encode_bit()
4 Correct 3 ms 4580 KB Output is correct - 282 call(s) of encode_bit()
5 Correct 30 ms 5756 KB Output is correct - 62932 call(s) of encode_bit()
6 Correct 28 ms 5788 KB Output is correct - 69932 call(s) of encode_bit()
7 Correct 48 ms 6032 KB Output is correct - 69932 call(s) of encode_bit()
8 Correct 26 ms 5548 KB Output is correct - 67202 call(s) of encode_bit()
9 Correct 27 ms 5596 KB Output is correct - 69932 call(s) of encode_bit()
10 Correct 28 ms 5604 KB Output is correct - 69932 call(s) of encode_bit()
11 Correct 32 ms 5748 KB Output is correct - 69932 call(s) of encode_bit()
12 Correct 27 ms 5712 KB Output is correct - 69932 call(s) of encode_bit()
13 Correct 56 ms 6304 KB Output is correct - 69932 call(s) of encode_bit()
14 Correct 28 ms 5692 KB Output is correct - 69932 call(s) of encode_bit()
15 Correct 28 ms 5716 KB Output is correct - 69932 call(s) of encode_bit()
16 Correct 54 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
17 Correct 46 ms 6152 KB Output is correct - 69932 call(s) of encode_bit()
18 Correct 72 ms 6392 KB Output is correct - 69932 call(s) of encode_bit()
19 Correct 46 ms 5956 KB Output is correct - 69932 call(s) of encode_bit()
20 Correct 60 ms 6684 KB Output is correct - 69932 call(s) of encode_bit()
21 Correct 94 ms 6860 KB Output is correct - 69932 call(s) of encode_bit()
22 Correct 63 ms 6224 KB Output is correct - 69932 call(s) of encode_bit()
23 Correct 106 ms 7000 KB Output is correct - 69932 call(s) of encode_bit()