Submission #1227723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227723		amine_aroua	Two Transportations (JOI19_transportations)	C++20	0 / 100	176 ms	13380 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = (1<<20) - 1;
// (dist , node) -> 20 + 10 = 30
vector<vector<pair<int ,int>>> adj;
vector<bool> vis;
priority_queue<pair<int ,int>,vector<pair<int ,int>> , greater<pair<int ,int>> > pq;
vector<int> dist ;
int n , a;
int nA = 0 , dA = 0;
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 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);
	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;
	nA = dA = 0;
	pq.push({0 , 0});
	code(0 , 0);
}
vector<int> batch;

pair<int ,int> decode()
{
	int dA = 0 , nA = 0;
	for(int i = 0 ; i < 20 ; i++)
		dA|=(batch[i]<<i);
	for(int i = 0 ;i < 10 ; i++)
		nA|=(batch[i + 20]<<i);
	return {dA , nA};
}
void upd(int N , int D)
{
	for(auto [u , c] : adj[N])
	{
		if(dist[u] > D + c)
		{
			// cout<<u<<'\n';
			dist[u] = D + c;
			pq.push({D + c , u});
		}
	}
}
void ReceiveA(bool x) {
	batch.push_back(x);
	if((int)batch.size() == 30)
	{
		auto [dB , nB] = decode();
		if(nA == n && nB == n)
		{
			return ;
		}
		int candN = nA , candD = dA;
		if(dA > dB)
		{
			candN = nB;
			candD = dB;
			dist[nB] = dB;
		}
		else
		{
			pq.pop();
		}
		if(nA != nB)
		{
			if(!vis[nB] && dist[nB] > dB)
			{
				dist[nB] = dB;
				pq.push({dB , nB});
			}
		}
		vis[candN] = 1;
		// cout<<"A : "<<candN<<" "<<candD<<'\n';
		upd(candN , candD);

		while(!pq.empty() && vis[pq.top().second])
			pq.pop();
		nA = n , dA = INF;
		if(!pq.empty())
		{
			nA = pq.top().second;
			dA = pq.top().first;
		}
		// cout<<"d : "<<dA<<" "<<nA<<'\n';
		code(dA , nA);
		batch.clear();
	}	
}

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

Baijan

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

const int INF_ = (1<<20) - 1;
// (dist_ , node) -> 20 + 10 = 30
vector<vector<pair<int ,int>>> adj_;
vector<bool> vis_;
priority_queue<pair<int ,int>,vector<pair<int ,int>> ,greater<pair<int ,int>> > pq_;
vector<int> dist_;
int n_ , b_;
int nB = 0 , dB = 0;
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_);
	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;
	nB = dB = 0;
	pq_.push({0 , 0});
	code_(0 , 0);
}
vector<int> batch_;
pair<int ,int> decode_()
{
	int dA = 0 , nA = 0;
	for(int i = 0 ; i < 20 ; i++)
		dA|=(batch_[i]<<i);
	for(int i = 0 ;i < 10 ; i++)
		nA|=(batch_[i + 20]<<i);
	return {dA , nA};
}

void upd_(int N , int D)
{
	for(auto [u , c] : adj_[N])
	{
			
		if(dist_[u] > D + c)
		{
			dist_[u] = D + c;
			// cout<<"B : "<<u<<'\n';
			pq_.push({D + c , u});
		}
	}
}

void ReceiveB(bool y) 
{
	batch_.push_back(y);
	if((int)batch_.size() == 30)
	{
		auto [dA , nA] = decode_();
		if(nB == n_ && nA == n_)
		{
			return ;
		}
		int candN = nB , candD = dB;
		if(nA == nB)
		{
			pq_.pop();
			candN = nB;
		}
		else
		{
			if(!vis_[nA] && dist_[nA] > dA)
			{
				dist_[nA] = dA;
				pq_.push({dA , nA});
			}
			if(dA <= dB)
			{
				candN = nA;
				candD = dA;
				dist_[nA] = dA;
			}
			else
			{
				pq_.pop();
			}
		}
		vis_[candN] = 1;
		// cout<<"B : "<<candN<<" "<<candD<<'\n';
		upd_(candN , candD);

		while(!pq_.empty() && vis_[pq_.top().second])
			pq_.pop();
		nB = n_ , dB = INF_;
		if(!pq_.empty())
		{
			nB = pq_.top().second;
			dB = pq_.top().first;
		}
		// cout<<"NB : "<<nB<<'\n';
		code_(dB , nB);
		batch_.clear();
	}	
}

• 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