oj.uz

Submission #613914

# Submission time Handle Problem Language Result Execution time Memory
613914 2022-07-30T13:14:37 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 1804 ms 59868 KB 
#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 = 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()
{
	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;
}
#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 = 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()
{
	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.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 380 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 516 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 456 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 728 KB Output is correct
2 Correct 405 ms 700 KB Output is correct
3 Correct 616 ms 13272 KB Output is correct
4 Correct 301 ms 656 KB Output is correct
5 Correct 554 ms 10176 KB Output is correct
6 Correct 331 ms 656 KB Output is correct
7 Correct 349 ms 656 KB Output is correct
8 Correct 346 ms 784 KB Output is correct
9 Correct 946 ms 30336 KB Output is correct
10 Correct 1057 ms 30224 KB Output is correct
11 Correct 1804 ms 59868 KB Output is correct
12 Correct 1494 ms 53284 KB Output is correct
13 Correct 395 ms 1028 KB Output is correct
14 Runtime error 2 ms 584 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 728 KB Output is correct
2 Correct 405 ms 700 KB Output is correct
3 Correct 616 ms 13272 KB Output is correct
4 Correct 301 ms 656 KB Output is correct
5 Correct 554 ms 10176 KB Output is correct
6 Correct 331 ms 656 KB Output is correct
7 Correct 349 ms 656 KB Output is correct
8 Correct 346 ms 784 KB Output is correct
9 Correct 946 ms 30336 KB Output is correct
10 Correct 1057 ms 30224 KB Output is correct
11 Correct 1804 ms 59868 KB Output is correct
12 Correct 1494 ms 53284 KB Output is correct
13 Correct 395 ms 1028 KB Output is correct
14 Runtime error 2 ms 584 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 728 KB Output is correct
2 Correct 405 ms 700 KB Output is correct
3 Correct 616 ms 13272 KB Output is correct
4 Correct 301 ms 656 KB Output is correct
5 Correct 554 ms 10176 KB Output is correct
6 Correct 331 ms 656 KB Output is correct
7 Correct 349 ms 656 KB Output is correct
8 Correct 346 ms 784 KB Output is correct
9 Correct 946 ms 30336 KB Output is correct
10 Correct 1057 ms 30224 KB Output is correct
11 Correct 1804 ms 59868 KB Output is correct
12 Correct 1494 ms 53284 KB Output is correct
13 Correct 395 ms 1028 KB Output is correct
14 Runtime error 2 ms 584 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 380 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -