oj.uz

답안 #613915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613915 2022-07-30T13:15:42 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 2014 ms 59956 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 = 4'000;
const int inf = 1'000'001;

const int ul = 20;
const int dl = 20;

int N;
vpii edge[mx];

vi dist0;

set<pii> destinations;

int curr_it; //0 to N-1
int curr_phase; //0 to 1
int curr_bit; //0 to dl-1 or ul-1

int rec_dist;
int rec_loc;

int my_dist;
int my_loc;

pii getnext()
{
	if(destinations.empty())
			while(1);
	pii z = *destinations.begin();

	if(z.second == -1)
		return z;

	
	if(dist0[z.second] <= z.first)
	{
		// cerr << "invoke\n";
		

		destinations.erase(destinations.begin());
		return getnext();
	}
	else
	{
		// cerr << "Azer get next : " << z.second << ' ' << dist0[z.second] << " at " << z.first << '\n';
		return z;
	}
}

void visit_node(int u, int d)
{
	dist0[u] = d;
	for(pii vp : edge[u])
	{
		// cerr << "Azer new destination " << vp.second << " at " << vp.first+d << '\n';
		destinations.insert({vp.first + d, vp.second});
	}
	pii mp = getnext();
	my_dist = mp.first;
	my_loc = mp.second;
}

void send_my_dist()
{
	// cerr << "iteration " << curr_it << " : Azer sends dist " << my_dist << '\n';
	// cerr << "node = " << my_loc << '\n';
	for(int b = 0; b < dl; b++)
		SendA(my_dist & (1<<b));
}

void send_my_loc()
{
	// cerr << "iteration " << curr_it << " : Azer sends loc " << my_loc << '\n';
	for(int b = 0; b < ul; b++)
		SendA(my_loc & (1<<b));
}


											}

//ALL PAIRS USE {DISTANCE, NODE}



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({C[j], V[j]});
		edge[V[j]].push_back({C[j], U[j]});
	}

	destinations.insert({inf, -1});
	dist0 = vi(N, inf);

	visit_node(0, 0);

	curr_it = 0;
	curr_phase = 0;
	curr_bit = 0;

	rec_dist = 0;
	rec_loc = 0;

	send_my_dist();
}

void ReceiveA(bool x_)
{
	int x = x_;

	if(curr_phase == 0)
	{
		rec_dist += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == dl)
		{
			if(my_dist <= rec_dist)
			{
				send_my_loc();

				curr_phase = 0;
				curr_it++;
				visit_node(my_loc, my_dist);
				if(curr_it < N-1) send_my_dist();
				rec_dist = 0;
				curr_bit = 0;

				// cerr << curr_it << " -> " << "Azer confirms his own location " << my_loc << " with distance " << my_dist << '\n';
				
			}
			else
			{
				curr_phase = 1;
				curr_bit = 0;
				// cerr << curr_it << " -> " << "Azer accepts Baijan has better\n";
			}
		}
	}
	else if(curr_phase == 1)
	{
		rec_loc += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == ul)
		{
			// cerr << curr_it << " -> " << "Azer accepts Baijan's location " << rec_loc << " with distance " << rec_dist << '\n';
			visit_node(rec_loc, rec_dist);

			curr_phase = 0;
			curr_bit = 0;
			curr_it++;
			if(curr_it < N-1) 
			{
				// cerr << "hello from Azer\n";
				send_my_dist();
			}
			rec_dist = 0;
			rec_loc = 0;
		}
	}
}

vi Answer()
{
	return dist0;
}
#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 = 4'000;
const int inf = 1'000'001;

const int ul = 20;
const int dl = 20;

int N;
vpii edge[mx];

vi dist0;

set<pii> destinations;

int curr_it; //0 to N-1
int curr_phase; //0 to 1
int curr_bit; //0 to dl-1 or ul-1

int rec_dist;
int rec_loc;

int my_dist;
int my_loc;

pii getnext()
{
	if(destinations.empty())
			while(1);
	pii z = *destinations.begin();

	if(z.second == -1)
		return z;

	if(dist0[z.second] <= z.first)
	{

		destinations.erase(destinations.begin());
		return getnext();
	}
	else
		return z;
}

void visit_node(int u, int d)
{
	dist0[u] = d;
	for(pii vp : edge[u])
		destinations.insert({vp.first + d, vp.second});
	pii mp = getnext();
	my_dist = mp.first;
	my_loc = mp.second;
}

void send_my_dist()
{
	// cerr << "iteration " << curr_it << " : Baijan sends dist " << my_dist << '\n';
	for(int b = 0; b < dl; b++)
		SendB(my_dist & (1<<b));
}

void send_my_loc()
{
	// cerr << "iteration " << curr_it << " : Baijan sends location " << my_loc << '\n';
	for(int b = 0; b < ul; b++)
		SendB(my_loc & (1<<b));
}

											}

//ALL PAIRS USE {DISTANCE, NODE}



void InitB(int N_, int B, vi S, vi T, vi D)
{
	N = N_;

	for(int j = 0; j < B; j++)
	{
		edge[S[j]].push_back({D[j], T[j]});
		edge[T[j]].push_back({D[j], S[j]});
	}

	destinations.insert({inf, -1});
	dist0 = vi(N, inf);

	visit_node(0, 0);

	curr_it = 0;
	curr_phase = 0;
	curr_bit = 0;

	rec_dist = 0;
	rec_loc = 0;

	pii mp = getnext();
	my_dist = mp.first;
    my_loc = mp.second;


	send_my_dist();
}

void ReceiveB(bool x_)
{
	int x = x_;

	if(curr_phase == 0)
	{
		rec_dist += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == dl)
		{
			if(my_dist < rec_dist)
			{
				send_my_loc();

				curr_phase = 0;
				curr_it++;
				visit_node(my_loc, my_dist);
				if(curr_it < N-1) send_my_dist();
				rec_dist = 0;
				curr_bit = 0;

				// cerr << curr_it << " -> " << "Baijan confirms his own location " << my_loc << " with distance " << my_dist << '\n';				
				
			}
			else
			{
				curr_phase = 1;
				curr_bit = 0;
				// cerr << curr_it << " -> Baijan accepts Azer has better\n";
			}
		}
	}
	else if(curr_phase == 1)
	{
		rec_loc += x * (1<<curr_bit);
		curr_bit++;

		if(curr_bit == ul)
		{
			// cerr << curr_it << " -> " << "Baijan accepts Azer's location " << rec_loc << " with distance " << rec_dist << '\n';
			visit_node(rec_loc, rec_dist);

			curr_phase = 0;
			curr_bit = 0;
			curr_it++;
			if(curr_it < N-1) send_my_dist();

			rec_dist = 0;
			rec_loc = 0;
		}
	}
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 300 ms 372 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 516 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 273 ms 456 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 561 ms 752 KB Output is correct
2 Correct 410 ms 700 KB Output is correct
3 Correct 643 ms 13368 KB Output is correct
4 Correct 411 ms 704 KB Output is correct
5 Correct 665 ms 10052 KB Output is correct
6 Correct 507 ms 744 KB Output is correct
7 Correct 412 ms 656 KB Output is correct
8 Correct 451 ms 912 KB Output is correct
9 Correct 1157 ms 30172 KB Output is correct
10 Correct 1060 ms 30240 KB Output is correct
11 Correct 2014 ms 59956 KB Output is correct
12 Correct 1570 ms 53432 KB Output is correct
13 Correct 342 ms 1036 KB Output is correct
14 Runtime error 2 ms 584 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 561 ms 752 KB Output is correct
2 Correct 410 ms 700 KB Output is correct
3 Correct 643 ms 13368 KB Output is correct
4 Correct 411 ms 704 KB Output is correct
5 Correct 665 ms 10052 KB Output is correct
6 Correct 507 ms 744 KB Output is correct
7 Correct 412 ms 656 KB Output is correct
8 Correct 451 ms 912 KB Output is correct
9 Correct 1157 ms 30172 KB Output is correct
10 Correct 1060 ms 30240 KB Output is correct
11 Correct 2014 ms 59956 KB Output is correct
12 Correct 1570 ms 53432 KB Output is correct
13 Correct 342 ms 1036 KB Output is correct
14 Runtime error 2 ms 584 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 561 ms 752 KB Output is correct
2 Correct 410 ms 700 KB Output is correct
3 Correct 643 ms 13368 KB Output is correct
4 Correct 411 ms 704 KB Output is correct
5 Correct 665 ms 10052 KB Output is correct
6 Correct 507 ms 744 KB Output is correct
7 Correct 412 ms 656 KB Output is correct
8 Correct 451 ms 912 KB Output is correct
9 Correct 1157 ms 30172 KB Output is correct
10 Correct 1060 ms 30240 KB Output is correct
11 Correct 2014 ms 59956 KB Output is correct
12 Correct 1570 ms 53432 KB Output is correct
13 Correct 342 ms 1036 KB Output is correct
14 Runtime error 2 ms 584 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 300 ms 372 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -