oj.uz

Submission #648256

# Submission time Handle Problem Language Result Execution time Memory
648256 2022-10-05T19:52:34 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 1738 ms 59792 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)
{
	N = N_;
	while(N <= 5);

	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 506 ms 792 KB Output is correct
2 Runtime error 387 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 324 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 419 ms 732 KB Output is correct
2 Incorrect 233 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 259 ms 692 KB Output is correct
2 Correct 216 ms 656 KB Output is correct
3 Correct 459 ms 13172 KB Output is correct
4 Correct 165 ms 656 KB Output is correct
5 Correct 419 ms 10080 KB Output is correct
6 Correct 191 ms 656 KB Output is correct
7 Correct 186 ms 656 KB Output is correct
8 Correct 230 ms 720 KB Output is correct
9 Correct 860 ms 30232 KB Output is correct
10 Correct 895 ms 30256 KB Output is correct
11 Correct 1738 ms 59792 KB Output is correct
12 Correct 1372 ms 53140 KB Output is correct
13 Correct 251 ms 924 KB Output is correct
14 Runtime error 347 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 259 ms 692 KB Output is correct
2 Correct 216 ms 656 KB Output is correct
3 Correct 459 ms 13172 KB Output is correct
4 Correct 165 ms 656 KB Output is correct
5 Correct 419 ms 10080 KB Output is correct
6 Correct 191 ms 656 KB Output is correct
7 Correct 186 ms 656 KB Output is correct
8 Correct 230 ms 720 KB Output is correct
9 Correct 860 ms 30232 KB Output is correct
10 Correct 895 ms 30256 KB Output is correct
11 Correct 1738 ms 59792 KB Output is correct
12 Correct 1372 ms 53140 KB Output is correct
13 Correct 251 ms 924 KB Output is correct
14 Runtime error 347 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 259 ms 692 KB Output is correct
2 Correct 216 ms 656 KB Output is correct
3 Correct 459 ms 13172 KB Output is correct
4 Correct 165 ms 656 KB Output is correct
5 Correct 419 ms 10080 KB Output is correct
6 Correct 191 ms 656 KB Output is correct
7 Correct 186 ms 656 KB Output is correct
8 Correct 230 ms 720 KB Output is correct
9 Correct 860 ms 30232 KB Output is correct
10 Correct 895 ms 30256 KB Output is correct
11 Correct 1738 ms 59792 KB Output is correct
12 Correct 1372 ms 53140 KB Output is correct
13 Correct 251 ms 924 KB Output is correct
14 Runtime error 347 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 506 ms 792 KB Output is correct
2 Runtime error 387 ms 328 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -