Submission #1227525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227525		amine_aroua	Two Transportations (JOI19_transportations)	C++20	0 / 100	139 ms	1120 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
// (dist , node) -> 20 + 10 = 30
vector<vector<pair<int ,int>>> adj;
vector<bool> vis;
priority_queue<pair<int ,int> > pq;
vector<int> dist , finaldist;
int n , a;
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) 
{
	n = N;
	a = A;
	adj.assign(N , {});
	dist.assign(N , INF);
	finaldist = dist;
	pq.push({0 , 0});
	vis.assign(N , 0);
	for(int i = 0 ; i < a ; i++)
	{
		adj[U[i]].push_back({V[i] , C[i]});
		adj[V[i]].push_back({U[i] , C[i]});
	}
	dist[0]=0;
	finaldist[0] = 0;
}
vector<int> batch;
void code(int a , int b)
{
	for(int i = 0 ;i < 20 ; i++)
	{
		int bit = ((a >> i)&1);
		SendA(bit);
	}
	for(int i = 0 ; i < 10 ; i++)
	{
		int bit = ((b >> i)&1);
		SendA(bit);
	}
}
void ReceiveA(bool x) {
	batch.push_back(x);
	if((int)batch.size() == 30)
	{
		vector<pair<int ,int>> cand;

		// Node from B
		int d2 = 0 , n2 = 0;
		for(int i = 0 ; i < 20 ; i++)
		{
			d2|=(batch[i]<<i);
		}
		for(int i = 0 ;i < 10 ; i++)
		{
			n2|=(batch[i + 20]<<i);
		}
		batch.clear();
		if(n2 < n)
		{
			finaldist[n2] = min(finaldist[n2] , d2);
			cand.push_back({d2 , n2});
		}

		// Node from A
		int n1 = n , d1 = 0;
		if(!pq.empty())
		{
			n1 = pq.top().second;
			d1 = -pq.top().first;
			pq.pop();
			if(!vis[n1])
			{
				vis[n1] = 1;
				cand.push_back({d1 , n1});
			}
		}
	
		if(cand.empty())
		{
			code(d1 , n1);
			return ;
		}
		//process
		for(auto [d , node] : cand)
		{
			assert(d >= 0);
			for(auto [u , c] : adj[node])
			{
				if(dist[u] > d + c)
				{
					dist[u] = d + c;
					finaldist[u] = min(finaldist[u] , d + c);
					pq.push({-(d + c), u});
				}
			}
		}

		// send Node A to B
		code(d1 , n1);
	}
}

std::vector<int> Answer() {
	for(int i = 0 ; i < n ; i++)
	{
		// assert(finaldist[i] != INF);
	}
	return finaldist;
}

Baijan

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;

const int INF_ = 1e9;
// (dist_ , node) -> 20 + 10 = 30
vector<vector<pair<int ,int>>> adj_;
vector<bool> vis_;
priority_queue<pair<int ,int> > pq_;
vector<int> dist_;
int n_ , b_;

void code_(int a , int b)
{
	for(int i = 0 ;i < 20 ; i++)
	{
		int bit = ((a >> i)&1);
		SendB(bit);
	}
	for(int i = 0 ; i < 10 ; i++)
	{
		int bit = ((b >> i)&1);
		SendB(bit);
	}
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D) {
	n_ = N;
	b_ = B;
	adj_.assign(N , {});
	dist_.assign(N , INF_);
	pq_.push({0 , 0});
	vis_.assign(N , 0);
	for(int i = 0 ; i < b_ ; i++)
	{
		adj_[S[i]].push_back({T[i] , D[i]});
		adj_[T[i]].push_back({S[i] , D[i]});
	}	
	dist_[0]=0;
	code_(0 , 0);
}
vector<int> batch_;
bool fr = 1;
void ReceiveB(bool y) 
{
	batch_.push_back(y);
	if((int)batch_.size() == 30)
	{
		vector<pair<int ,int>> cand;

		// Node from A
		int d2 = 0 , n2 = 0;
		for(int i = 0 ; i < 20 ; i++)
		{
			d2|=(batch_[i]<<i);
		}
		for(int i = 0 ;i < 10 ; i++)
		{
			n2|=(batch_[i + 20]<<i);
		}
		batch_.clear();
		if(n2 < n_)
			cand.push_back({d2 , n2});

		// Node from B
		int n1 = n_ , d1 = 0;
		if(!pq_.empty())
		{
			n1 = pq_.top().second;
			d1 = -pq_.top().first;
			pq_.pop();
			if(!vis_[n1])
			{
				vis_[n1] = 1;
				cand.push_back({d1 , n1});
			}
		}

		if(cand.empty())
		{
			if(fr)
			{
				fr = 0;
				for(int i = 0 ; i <n_ ; i++)
				{
					code_(dist_[i] , i);
				}
			}
			return;
		}
		//process
		for(auto [d , node] : cand)
		{
			assert(d >= 0);
			for(auto [u , c] : adj_[node])
			{
				if(dist_[u] > d + c)
				{
					dist_[u] = d + c;
					pq_.push({-(d + c) , u});
				}
			}
		}

		// send Node B to A
		code_(d1 , n1);
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16