oj.uz

Submission #648241

# Submission time Handle Problem Language Result Execution time Memory
648241 2022-10-05T19:41:33 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 1791 ms 59940 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_;

	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 590 ms 808 KB Output is correct
2 Incorrect 402 ms 328 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 728 KB Output is correct
2 Runtime error 379 ms 340 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 244 ms 688 KB Output is correct
2 Correct 182 ms 680 KB Output is correct
3 Correct 407 ms 13316 KB Output is correct
4 Correct 247 ms 680 KB Output is correct
5 Correct 439 ms 10068 KB Output is correct
6 Correct 198 ms 656 KB Output is correct
7 Correct 264 ms 668 KB Output is correct
8 Correct 174 ms 744 KB Output is correct
9 Correct 929 ms 30224 KB Output is correct
10 Correct 919 ms 30264 KB Output is correct
11 Correct 1791 ms 59940 KB Output is correct
12 Correct 1406 ms 53160 KB Output is correct
13 Correct 202 ms 1020 KB Output is correct
14 Incorrect 265 ms 328 KB Wrong Answer [2]
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 688 KB Output is correct
2 Correct 182 ms 680 KB Output is correct
3 Correct 407 ms 13316 KB Output is correct
4 Correct 247 ms 680 KB Output is correct
5 Correct 439 ms 10068 KB Output is correct
6 Correct 198 ms 656 KB Output is correct
7 Correct 264 ms 668 KB Output is correct
8 Correct 174 ms 744 KB Output is correct
9 Correct 929 ms 30224 KB Output is correct
10 Correct 919 ms 30264 KB Output is correct
11 Correct 1791 ms 59940 KB Output is correct
12 Correct 1406 ms 53160 KB Output is correct
13 Correct 202 ms 1020 KB Output is correct
14 Incorrect 265 ms 328 KB Wrong Answer [2]
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 688 KB Output is correct
2 Correct 182 ms 680 KB Output is correct
3 Correct 407 ms 13316 KB Output is correct
4 Correct 247 ms 680 KB Output is correct
5 Correct 439 ms 10068 KB Output is correct
6 Correct 198 ms 656 KB Output is correct
7 Correct 264 ms 668 KB Output is correct
8 Correct 174 ms 744 KB Output is correct
9 Correct 929 ms 30224 KB Output is correct
10 Correct 919 ms 30264 KB Output is correct
11 Correct 1791 ms 59940 KB Output is correct
12 Correct 1406 ms 53160 KB Output is correct
13 Correct 202 ms 1020 KB Output is correct
14 Incorrect 265 ms 328 KB Wrong Answer [2]
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 808 KB Output is correct
2 Incorrect 402 ms 328 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -