Submission #613897

#	Time	Username	Problem	Language	Result	Execution time	Memory
613897		blue	Two Transportations (JOI19_transportations)	C++17	0 / 100	206 ms	656 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 = 2'000;
const int inf = 1'000'001;

const int ul = 11;
const int dl = 20;

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()
{
	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});
}

void send_my_dist()
{
	for(int b = 0; b < dl; b++)
		SendA(my_dist & (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;

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

	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)
			{
				for(int b = 0; b < ul; b++)
				{
					SendA(my_loc & (1<<b));
				}

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

				visit_node(my_loc, my_dist);
				pii mp = getnext();
				my_dist = mp.first;
   				my_loc = mp.second;
			}
			else
			{
				curr_phase = 1;
				curr_bit = 0;
			}
		}
	}
	else if(curr_phase == 1)
	{
		rec_loc += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == ul)
		{
			visit_node(rec_loc, rec_dist);
			pii mp = getnext();

			my_dist = mp.first;
			my_loc = mp.second;

			curr_phase = 0;
			curr_bit = 0;
			curr_it++;
			if(curr_it < N-1) 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 = 2'000;
const int inf = 1'000'001;

const int ul = 11;
const int dl = 20;

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()
{
	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});
}

void send_my_dist()
{
	for(int b = 0; b < dl; b++)
		SendB(my_dist & (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)
			{
				for(int b = 0; b < ul; b++)
				{
					SendB(my_loc & (1<<b));
				}

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

				visit_node(my_loc, my_dist);
				pii mp = getnext();
				my_dist = mp.first;
   				my_loc = mp.second;
			}
			else
			{
				curr_phase = 1;
				curr_bit = 0;
			}
		}
	}
	else if(curr_phase == 1)
	{
		rec_loc += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == ul)
		{
			visit_node(rec_loc, rec_dist);
			pii mp = getnext();
			
			my_dist = mp.first;
			my_loc = mp.second;

			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: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16