oj.uz

Submission #648249

# Submission time Handle Problem Language Result Execution time Memory
648249 2022-10-05T19:48:15 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 2413 ms 59872 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 <= 7);
	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 497 ms 788 KB Output is correct
2 Runtime error 269 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 237 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 436 ms 732 KB Output is correct
2 Incorrect 336 ms 328 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 684 KB Output is correct
2 Correct 210 ms 656 KB Output is correct
3 Correct 511 ms 13300 KB Output is correct
4 Correct 237 ms 708 KB Output is correct
5 Correct 393 ms 10068 KB Output is correct
6 Correct 160 ms 700 KB Output is correct
7 Correct 199 ms 656 KB Output is correct
8 Correct 270 ms 656 KB Output is correct
9 Correct 987 ms 30216 KB Output is correct
10 Correct 986 ms 30300 KB Output is correct
11 Correct 2413 ms 59872 KB Output is correct
12 Correct 1431 ms 53324 KB Output is correct
13 Correct 248 ms 1280 KB Output is correct
14 Runtime error 369 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 229 ms 684 KB Output is correct
2 Correct 210 ms 656 KB Output is correct
3 Correct 511 ms 13300 KB Output is correct
4 Correct 237 ms 708 KB Output is correct
5 Correct 393 ms 10068 KB Output is correct
6 Correct 160 ms 700 KB Output is correct
7 Correct 199 ms 656 KB Output is correct
8 Correct 270 ms 656 KB Output is correct
9 Correct 987 ms 30216 KB Output is correct
10 Correct 986 ms 30300 KB Output is correct
11 Correct 2413 ms 59872 KB Output is correct
12 Correct 1431 ms 53324 KB Output is correct
13 Correct 248 ms 1280 KB Output is correct
14 Runtime error 369 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 229 ms 684 KB Output is correct
2 Correct 210 ms 656 KB Output is correct
3 Correct 511 ms 13300 KB Output is correct
4 Correct 237 ms 708 KB Output is correct
5 Correct 393 ms 10068 KB Output is correct
6 Correct 160 ms 700 KB Output is correct
7 Correct 199 ms 656 KB Output is correct
8 Correct 270 ms 656 KB Output is correct
9 Correct 987 ms 30216 KB Output is correct
10 Correct 986 ms 30300 KB Output is correct
11 Correct 2413 ms 59872 KB Output is correct
12 Correct 1431 ms 53324 KB Output is correct
13 Correct 248 ms 1280 KB Output is correct
14 Runtime error 369 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 497 ms 788 KB Output is correct
2 Runtime error 269 ms 328 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -