oj.uz

Submission #648244

# Submission time Handle Problem Language Result Execution time Memory
648244 2022-10-05T19:44:05 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 1707 ms 60004 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
			{
				// while(1);
				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 426 ms 904 KB Output is correct
2 Incorrect 288 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 349 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 579 ms 736 KB Output is correct
2 Incorrect 360 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 226 ms 680 KB Output is correct
2 Correct 250 ms 656 KB Output is correct
3 Correct 431 ms 13180 KB Output is correct
4 Correct 230 ms 656 KB Output is correct
5 Correct 376 ms 10068 KB Output is correct
6 Correct 196 ms 696 KB Output is correct
7 Correct 251 ms 656 KB Output is correct
8 Correct 197 ms 656 KB Output is correct
9 Correct 974 ms 30216 KB Output is correct
10 Correct 902 ms 30236 KB Output is correct
11 Correct 1707 ms 60004 KB Output is correct
12 Correct 1505 ms 53344 KB Output is correct
13 Correct 198 ms 968 KB Output is correct
14 Runtime error 258 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 226 ms 680 KB Output is correct
2 Correct 250 ms 656 KB Output is correct
3 Correct 431 ms 13180 KB Output is correct
4 Correct 230 ms 656 KB Output is correct
5 Correct 376 ms 10068 KB Output is correct
6 Correct 196 ms 696 KB Output is correct
7 Correct 251 ms 656 KB Output is correct
8 Correct 197 ms 656 KB Output is correct
9 Correct 974 ms 30216 KB Output is correct
10 Correct 902 ms 30236 KB Output is correct
11 Correct 1707 ms 60004 KB Output is correct
12 Correct 1505 ms 53344 KB Output is correct
13 Correct 198 ms 968 KB Output is correct
14 Runtime error 258 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 226 ms 680 KB Output is correct
2 Correct 250 ms 656 KB Output is correct
3 Correct 431 ms 13180 KB Output is correct
4 Correct 230 ms 656 KB Output is correct
5 Correct 376 ms 10068 KB Output is correct
6 Correct 196 ms 696 KB Output is correct
7 Correct 251 ms 656 KB Output is correct
8 Correct 197 ms 656 KB Output is correct
9 Correct 974 ms 30216 KB Output is correct
10 Correct 902 ms 30236 KB Output is correct
11 Correct 1707 ms 60004 KB Output is correct
12 Correct 1505 ms 53344 KB Output is correct
13 Correct 198 ms 968 KB Output is correct
14 Runtime error 258 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 426 ms 904 KB Output is correct
2 Incorrect 288 ms 328 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -