oj.uz

답안 #613918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613918 2022-07-30T13:19:00 Z blue Two Transportations (JOI19_transportations) C++17
38 / 100
 2064 ms 59760 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 = 11;
const int dl = 19;

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 = 11;
const int dl = 19;

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 407 ms 380 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 656 KB Output is correct
2 Runtime error 326 ms 464 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 736 KB Output is correct
2 Correct 356 ms 704 KB Output is correct
3 Correct 718 ms 13400 KB Output is correct
4 Correct 402 ms 656 KB Output is correct
5 Correct 621 ms 10204 KB Output is correct
6 Correct 460 ms 656 KB Output is correct
7 Correct 359 ms 784 KB Output is correct
8 Correct 357 ms 896 KB Output is correct
9 Correct 1185 ms 30312 KB Output is correct
10 Correct 1218 ms 30324 KB Output is correct
11 Correct 2064 ms 59760 KB Output is correct
12 Correct 1484 ms 53300 KB Output is correct
13 Correct 266 ms 1044 KB Output is correct
14 Correct 2 ms 656 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 736 KB Output is correct
2 Correct 356 ms 704 KB Output is correct
3 Correct 718 ms 13400 KB Output is correct
4 Correct 402 ms 656 KB Output is correct
5 Correct 621 ms 10204 KB Output is correct
6 Correct 460 ms 656 KB Output is correct
7 Correct 359 ms 784 KB Output is correct
8 Correct 357 ms 896 KB Output is correct
9 Correct 1185 ms 30312 KB Output is correct
10 Correct 1218 ms 30324 KB Output is correct
11 Correct 2064 ms 59760 KB Output is correct
12 Correct 1484 ms 53300 KB Output is correct
13 Correct 266 ms 1044 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Correct 523 ms 748 KB Output is correct
16 Correct 391 ms 764 KB Output is correct
17 Incorrect 395 ms 656 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 736 KB Output is correct
2 Correct 356 ms 704 KB Output is correct
3 Correct 718 ms 13400 KB Output is correct
4 Correct 402 ms 656 KB Output is correct
5 Correct 621 ms 10204 KB Output is correct
6 Correct 460 ms 656 KB Output is correct
7 Correct 359 ms 784 KB Output is correct
8 Correct 357 ms 896 KB Output is correct
9 Correct 1185 ms 30312 KB Output is correct
10 Correct 1218 ms 30324 KB Output is correct
11 Correct 2064 ms 59760 KB Output is correct
12 Correct 1484 ms 53300 KB Output is correct
13 Correct 266 ms 1044 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Correct 523 ms 748 KB Output is correct
16 Correct 391 ms 764 KB Output is correct
17 Incorrect 395 ms 656 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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