Submission #613918

#	Time	Username	Problem	Language	Result	Execution time	Memory
613918		blue	Two Transportations (JOI19_transportations)	C++17	38 / 100	2064 ms	59760 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
 
									namespace{
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;

const int mx = 4'000;
const int inf = 1'000'001;

const int ul = 11;
const int dl = 19;

int N;
vpii edge[mx];

vi dist0;

set<pii> destinations;

int curr_it; //0 to N-1
int curr_phase; //0 to 1
int curr_bit; //0 to dl-1 or ul-1

int rec_dist;
int rec_loc;

int my_dist;
int my_loc;

pii getnext()
{
	if(destinations.empty())
			while(1);
	pii z = *destinations.begin();

	if(z.second == -1)
		return z;

	
	if(dist0[z.second] <= z.first)
	{
		// cerr << "invoke\n";
		

		destinations.erase(destinations.begin());
		return getnext();
	}
	else
	{
		// cerr << "Azer get next : " << z.second << ' ' << dist0[z.second] << " at " << z.first << '\n';
		return z;
	}
}

void visit_node(int u, int d)
{
	dist0[u] = d;
	for(pii vp : edge[u])
	{
		// cerr << "Azer new destination " << vp.second << " at " << vp.first+d << '\n';
		destinations.insert({vp.first + d, vp.second});
	}
	pii mp = getnext();
	my_dist = mp.first;
	my_loc = mp.second;
}

void send_my_dist()
{
	// cerr << "iteration " << curr_it << " : Azer sends dist " << my_dist << '\n';
	// cerr << "node = " << my_loc << '\n';
	for(int b = 0; b < dl; b++)
		SendA(my_dist & (1<<b));
}

void send_my_loc()
{
	// cerr << "iteration " << curr_it << " : Azer sends loc " << my_loc << '\n';
	for(int b = 0; b < ul; b++)
		SendA(my_loc & (1<<b));
}


											}

//ALL PAIRS USE {DISTANCE, NODE}



void InitA(int N_, int A, vi U, vi V, vi C)
{
	N = N_;

	for(int j = 0; j < A; j++)
	{
		edge[U[j]].push_back({C[j], V[j]});
		edge[V[j]].push_back({C[j], U[j]});
	}

	destinations.insert({inf, -1});
	dist0 = vi(N, inf);

	visit_node(0, 0);

	curr_it = 0;
	curr_phase = 0;
	curr_bit = 0;

	rec_dist = 0;
	rec_loc = 0;

	send_my_dist();
}

void ReceiveA(bool x_)
{
	int x = x_;

	if(curr_phase == 0)
	{
		rec_dist += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == dl)
		{
			if(my_dist <= rec_dist)
			{
				send_my_loc();

				curr_phase = 0;
				curr_it++;
				visit_node(my_loc, my_dist);
				if(curr_it < N-1) send_my_dist();
				rec_dist = 0;
				curr_bit = 0;

				// cerr << curr_it << " -> " << "Azer confirms his own location " << my_loc << " with distance " << my_dist << '\n';
				
			}
			else
			{
				curr_phase = 1;
				curr_bit = 0;
				// cerr << curr_it << " -> " << "Azer accepts Baijan has better\n";
			}
		}
	}
	else if(curr_phase == 1)
	{
		rec_loc += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == ul)
		{
			// cerr << curr_it << " -> " << "Azer accepts Baijan's location " << rec_loc << " with distance " << rec_dist << '\n';
			visit_node(rec_loc, rec_dist);

			curr_phase = 0;
			curr_bit = 0;
			curr_it++;
			if(curr_it < N-1) 
			{
				// cerr << "hello from Azer\n";
				send_my_dist();
			}
			rec_dist = 0;
			rec_loc = 0;
		}
	}
}

vi Answer()
{
	return dist0;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
 
									namespace{
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;

const int mx = 4'000;
const int inf = 1'000'001;

const int ul = 11;
const int dl = 19;

int N;
vpii edge[mx];

vi dist0;

set<pii> destinations;

int curr_it; //0 to N-1
int curr_phase; //0 to 1
int curr_bit; //0 to dl-1 or ul-1

int rec_dist;
int rec_loc;

int my_dist;
int my_loc;

pii getnext()
{
	if(destinations.empty())
			while(1);
	pii z = *destinations.begin();

	if(z.second == -1)
		return z;

	if(dist0[z.second] <= z.first)
	{

		destinations.erase(destinations.begin());
		return getnext();
	}
	else
		return z;
}

void visit_node(int u, int d)
{
	dist0[u] = d;
	for(pii vp : edge[u])
		destinations.insert({vp.first + d, vp.second});
	pii mp = getnext();
	my_dist = mp.first;
	my_loc = mp.second;
}

void send_my_dist()
{
	// cerr << "iteration " << curr_it << " : Baijan sends dist " << my_dist << '\n';
	for(int b = 0; b < dl; b++)
		SendB(my_dist & (1<<b));
}

void send_my_loc()
{
	// cerr << "iteration " << curr_it << " : Baijan sends location " << my_loc << '\n';
	for(int b = 0; b < ul; b++)
		SendB(my_loc & (1<<b));
}

											}

//ALL PAIRS USE {DISTANCE, NODE}



void InitB(int N_, int B, vi S, vi T, vi D)
{
	N = N_;

	for(int j = 0; j < B; j++)
	{
		edge[S[j]].push_back({D[j], T[j]});
		edge[T[j]].push_back({D[j], S[j]});
	}

	destinations.insert({inf, -1});
	dist0 = vi(N, inf);

	visit_node(0, 0);

	curr_it = 0;
	curr_phase = 0;
	curr_bit = 0;

	rec_dist = 0;
	rec_loc = 0;

	pii mp = getnext();
	my_dist = mp.first;
    my_loc = mp.second;


	send_my_dist();
}

void ReceiveB(bool x_)
{
	int x = x_;

	if(curr_phase == 0)
	{
		rec_dist += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == dl)
		{
			if(my_dist < rec_dist)
			{
				send_my_loc();

				curr_phase = 0;
				curr_it++;
				visit_node(my_loc, my_dist);
				if(curr_it < N-1) send_my_dist();
				rec_dist = 0;
				curr_bit = 0;

				// cerr << curr_it << " -> " << "Baijan confirms his own location " << my_loc << " with distance " << my_dist << '\n';				
				
			}
			else
			{
				curr_phase = 1;
				curr_bit = 0;
				// cerr << curr_it << " -> Baijan accepts Azer has better\n";
			}
		}
	}
	else if(curr_phase == 1)
	{
		rec_loc += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == ul)
		{
			// cerr << curr_it << " -> " << "Baijan accepts Azer's location " << rec_loc << " with distance " << rec_dist << '\n';
			visit_node(rec_loc, rec_dist);

			curr_phase = 0;
			curr_bit = 0;
			curr_it++;
			if(curr_it < N-1) send_my_dist();

			rec_dist = 0;
			rec_loc = 0;
		}
	}
}

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