oj.uz

Submission #648251

# Submission time Handle Problem Language Result Execution time Memory
648251 2022-10-05T19:49:25 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 1651 ms 59828 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 = 2'000;
	const int inf = 1'000'000'000;

	const int dl = 9;
	const int ul = 11;

	int N;
	vpii edge[mx];
	vi currdist;

	set<pii> options;

	pii get_option()
	{
		while(1)
		{
			if(options.empty())
				return {inf, 0};

			int d = options.begin()->first;
			int u = options.begin()->second;

			// cerr << "azer ";
			// cerr << d << ' ' << u << " : " << currdist[u] << '\n';

			// cerr << d << " -> " << u << '\n';
			// cerr << currdist[u] << '\n';

			if(d >= currdist[u])
			{
				// cerr << "terminated\n";
				options.erase(options.begin());
			}
			else
			{
				// cerr << "returned\n";
				return {d, u};
			}
		}
	}

	int lastdist = 0;

	int it = 0;
	int phase = 0;
	int bt = 0;

	int mydist = 0;
	int myloc = 0;

	int recdist = 0;
	int recloc = 0;

	int actdist = 0;
	int actloc = 0;
}

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

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

	currdist = vi(N, inf);
	currdist[0] = 0;

	for(pii e : edge[0])
		options.insert({e.second + 0, e.first});

	pii du = get_option();
	mydist = du.first;
	myloc = du.second;

	mydist = min(mydist, lastdist + 501);

	for(int b = 0; b < dl; b++)
		SendA((mydist - lastdist) & (1<<b));

	// cerr << "Azer first sends " << mydist << '\n'; 
}

void ReceiveA(bool x)
{
	if(phase == 0)
	{
		if(x)
			recdist += (1<<bt);
		bt++;
		if(bt == dl)
		{
			// cerr << it << "        Azer = " << mydist << "         Baijan = " << recdist << '\n';
			if(mydist < recdist) //MAKE SURE IT IS <= IN THE OTHER PROGRAM
			{
				for(int b = 0; b < ul; b++)
					SendA(myloc & (1<<b));
				actdist = mydist;
				actloc = myloc;
				//go down
			}
			else
			{
				phase = 1;
				bt = 0;
				// cerr << "Azer goes to phase " << 1 << '\n';
				return;
			}
		}
		else
			return;
	}
	else if(phase == 1)
	{
		// cerr << "Azer in phase 1 " << '\n';
		// cerr << "it = " << it << '\n';
		if(x)
			recloc += (1<<bt);
		bt++;
		if(bt < ul)
			return;
		else
		{
			// cerr << "Azer received best option from Baijan : " << recloc << " at " << recdist << '\n';
			actdist = recdist;
			actloc = recloc;
			//go down
		}
	}

	currdist[actloc] = actdist;
	for(pii vp : edge[actloc])
		options.insert({vp.second + actdist, vp.first});

	// cerr << "Azer activated outgoing edges from " << actloc << '\n';

	lastdist = max(lastdist, actdist);

	// cerr << "Azer : \n";
	// cerr << "phase " << it << " terminated\n";
	// for(int i = 0; i < N; i++)
	// 	cerr << currdist[i] << ' ';
	// cerr << '\n';

	it++;
	if(it == N-1)
		return;

	phase = 0;
	bt = 0;

	pii du = get_option();
	mydist = du.first;
	myloc = du.second;

mydist = min(mydist, lastdist + 501);
	for(int b = 0; b < dl; b++)
		SendA((mydist - lastdist) & (1<<b));

	recdist = lastdist;
	recloc = 0;
	// cerr << "\n\n\n\n";
}

vi Answer()
{
	return currdist;
}
#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'000'000;

	const int dl = 9;
	const int ul = 11;

	int N;
	vpii edge[mx];
	vi currdist;

	set<pii> options;

	pii get_option()
	{
		while(1)
		{
			if(options.empty())
			{
				// cerr << "Baijan returned empty\n";
				return {inf, 0};
			}

			int d = options.begin()->first;
			int u = options.begin()->second;

			// cerr << "baijan \n";
			// cerr << d << ' ' << u << " : " << currdist[u] << '\n';


			if(d >= currdist[u])
			{
				// cerr << "terminated\n";
				options.erase(options.begin());
			}
			else
			{
				// cerr << "returned\n";
				return {d, u};
			}
		}
	}

	int lastdist = 0;

	int it = 0;
	int phase = 0;
	int bt = 0;

	int mydist = 0;
	int myloc = 0;

	int recdist = 0;
	int recloc = 0;

	int actdist = 0;
	int actloc = 0;
}

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

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

	currdist = vi(N, inf);
	currdist[0] = 0;

	for(pii e : edge[0])
		options.insert({e.second + 0, e.first});

	pii du = get_option();
	mydist = du.first;
	myloc = du.second;

	mydist = min(mydist, lastdist + 501);

	for(int b = 0; b < dl; b++)
		SendB((mydist - lastdist) & (1<<b));

	// cerr << "Baijan first sends " << mydist << '\n'; 
}

void ReceiveB(bool x)
{
	if(phase == 0)
	{
		if(x)
			recdist += (1<<bt);
		bt++;
		if(bt == dl)
		{
			// cerr << "Baijan received option " << 
			if(mydist <= recdist)
			{
				// cerr << "Baijan sending location\n";
				for(int b = 0; b < ul; b++)
					SendB(myloc & (1<<b));
				actdist = mydist;
				actloc = myloc;
				//go down
				// cerr << "Baijan sent location " << myloc << " at " << mydist << '\n';
			}
			else
			{
				phase = 1;
				bt = 0;
				// cerr << "Baijan goes to phase 1\n";
				return;
			}
		}
		else
			return;
	}
	else if(phase == 1)
	{
		if(x)
			recloc += (1<<bt);
		bt++;
		if(bt < ul)
			return;
		else
		{
			actdist = recdist;
			actloc = recloc;
			//go down
		}
	}

	currdist[actloc] = actdist;
	for(pii vp : edge[actloc])
	{

		options.insert({vp.second + actdist, vp.first});
		// cerr << vp.first << " at " << vp.second + actdist << " : " << "Baijan" << '\n';
	}

	// cerr << "Baijan activated outgoing edges from " << actloc << '\n';

	lastdist = max(lastdist, actdist);

	// cerr << "Baijan : \n";
	// cerr << "phase " << it << " terminated\n";
	// for(int i = 0; i < N; i++)
	// 	cerr << currdist[i] << ' ';
	// cerr << '\n';

	it++;
	if(it == N-1)
		return;

	phase = 0;
	bt = 0;

	pii du = get_option();
	mydist = du.first;
	myloc = du.second;

	// cerr << "now my dist = " << mydist << '\n';
	// cerr << "lastdist = " << lastdist << '\n';

	mydist = min(mydist, lastdist + 501);

	for(int b = 0; b < dl; b++)
		SendB((mydist - lastdist) & (1<<b));
	// cerr << "Baijan sending distance " << mydist << " for " << myloc << '\n';

	recdist = lastdist;
	recloc = 0;
	// cerr << "\n\n\n\n";
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 784 KB Output is correct
2 Runtime error 442 ms 328 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 732 KB Output is correct
2 Runtime error 360 ms 328 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 692 KB Output is correct
2 Correct 243 ms 660 KB Output is correct
3 Correct 366 ms 13308 KB Output is correct
4 Correct 213 ms 668 KB Output is correct
5 Correct 419 ms 10072 KB Output is correct
6 Correct 227 ms 692 KB Output is correct
7 Correct 235 ms 656 KB Output is correct
8 Correct 145 ms 716 KB Output is correct
9 Correct 883 ms 30396 KB Output is correct
10 Correct 959 ms 30316 KB Output is correct
11 Correct 1651 ms 59828 KB Output is correct
12 Correct 1230 ms 52988 KB Output is correct
13 Correct 249 ms 984 KB Output is correct
14 Runtime error 352 ms 328 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 692 KB Output is correct
2 Correct 243 ms 660 KB Output is correct
3 Correct 366 ms 13308 KB Output is correct
4 Correct 213 ms 668 KB Output is correct
5 Correct 419 ms 10072 KB Output is correct
6 Correct 227 ms 692 KB Output is correct
7 Correct 235 ms 656 KB Output is correct
8 Correct 145 ms 716 KB Output is correct
9 Correct 883 ms 30396 KB Output is correct
10 Correct 959 ms 30316 KB Output is correct
11 Correct 1651 ms 59828 KB Output is correct
12 Correct 1230 ms 52988 KB Output is correct
13 Correct 249 ms 984 KB Output is correct
14 Runtime error 352 ms 328 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 692 KB Output is correct
2 Correct 243 ms 660 KB Output is correct
3 Correct 366 ms 13308 KB Output is correct
4 Correct 213 ms 668 KB Output is correct
5 Correct 419 ms 10072 KB Output is correct
6 Correct 227 ms 692 KB Output is correct
7 Correct 235 ms 656 KB Output is correct
8 Correct 145 ms 716 KB Output is correct
9 Correct 883 ms 30396 KB Output is correct
10 Correct 959 ms 30316 KB Output is correct
11 Correct 1651 ms 59828 KB Output is correct
12 Correct 1230 ms 52988 KB Output is correct
13 Correct 249 ms 984 KB Output is correct
14 Runtime error 352 ms 328 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 784 KB Output is correct
2 Runtime error 442 ms 328 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -