Submission #404916

#	Time	Username	Problem	Language	Result	Execution time	Memory
404916		Jasiekstrz	Saveit (IOI10_saveit)	C++17	50 / 100	329 ms	14404 KiB

encoder

#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
#define fi first
#define se second
using namespace std;
static const int NN=1e3;
static const int EE=NN*NN;
static vector<pair<int,int>> e[NN+10];
static bool vis[NN+10];
static bool enc[EE+10];
void send_int(int x)
{
	for(int i=9;i>=0;i--)
		encode_bit((x&(1<<i))!=0);
	return;
}
static void bfs(int x,int n)
{
	for(int i=0;i<n;i++)
		vis[i]=false;
	queue<int> qq;
	vis[x]=true;
	qq.push(x);
	while(!qq.empty())
	{
		x=qq.front();
		qq.pop();
		for(auto v:e[x])
		{
			if(!vis[v.fi])
			{
				vis[v.fi]=true;
				enc[v.se]=true;
				qq.push(v.fi);
			}
		}
	}
	return;
}
void encode(int nv,int nh,int ne,int *v1,int *v2)
{
	for(int i=0;i<ne;i++)
	{
		e[v1[i]].emplace_back(v2[i],i);
		e[v2[i]].emplace_back(v1[i],i);
	}
	for(int i=0;i<nh;i++)
		bfs(i,nv);
	for(int i=0;i<nv;i++)
	{
		vector<int> tmp;
		for(auto v:e[i])
		{
			if(enc[v.se])
			{
				tmp.push_back(v.fi);
				enc[v.se]=false;
			}
		}
		send_int(tmp.size());
		for(auto v:tmp)
			send_int(v);
	}
	return;
}

decoder

#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
#define fi first
#define se second
using namespace std;
static const int NN=1e3;
static vector<int> e[NN+10];
static bool vis[NN+10];
int receive_int()
{
	int ans=0;
	for(int i=0;i<10;i++)
		ans=(2*ans+decode_bit());
	return ans;
}
static void bfs(int x,int n)
{
	for(int i=0;i<n;i++)
		vis[i]=false;
	queue<pair<int,int>> qq;
	vis[x]=true;
	qq.push({x,0});
	while(!qq.empty())
	{
		auto y=qq.front();
		qq.pop();
		hops(x,y.fi,y.se);
		for(auto v:e[y.fi])
		{
			if(!vis[v])
			{
				vis[v]=true;
				qq.push({v,y.se+1});
			}
		}
	}
	return;
}
void decode(int nv,int nh)
{
	for(int i=0;i<nv;i++)
	{
		int d=receive_int();
		for(int j=0;j<d;j++)
		{
			int b=receive_int();
			e[i].push_back(b);
			e[b].push_back(i);
		}
	}
	for(int i=0;i<nh;i++)
		bfs(i,nv);
	return;
}

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