oj.uz

답안 #613909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613909 2022-07-30T13:06:09 Z blue Two Transportations (JOI19_transportations) C++17
0 / 100
 1930 ms 59836 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'001;

const int ul = 11;
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()
{
	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 = 2'000;
const int inf = 1'000'001;

const int ul = 11;
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()
{
	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 207 ms 332 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 684 KB Output is correct
2 Correct 289 ms 656 KB Output is correct
3 Correct 681 ms 13176 KB Output is correct
4 Correct 288 ms 656 KB Output is correct
5 Correct 623 ms 10064 KB Output is correct
6 Correct 386 ms 692 KB Output is correct
7 Correct 393 ms 656 KB Output is correct
8 Correct 324 ms 780 KB Output is correct
9 Correct 1036 ms 30332 KB Output is correct
10 Correct 1054 ms 30312 KB Output is correct
11 Correct 1930 ms 59836 KB Output is correct
12 Correct 1506 ms 53328 KB Output is correct
13 Correct 335 ms 1000 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 684 KB Output is correct
2 Correct 289 ms 656 KB Output is correct
3 Correct 681 ms 13176 KB Output is correct
4 Correct 288 ms 656 KB Output is correct
5 Correct 623 ms 10064 KB Output is correct
6 Correct 386 ms 692 KB Output is correct
7 Correct 393 ms 656 KB Output is correct
8 Correct 324 ms 780 KB Output is correct
9 Correct 1036 ms 30332 KB Output is correct
10 Correct 1054 ms 30312 KB Output is correct
11 Correct 1930 ms 59836 KB Output is correct
12 Correct 1506 ms 53328 KB Output is correct
13 Correct 335 ms 1000 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 343 ms 684 KB Output is correct
2 Correct 289 ms 656 KB Output is correct
3 Correct 681 ms 13176 KB Output is correct
4 Correct 288 ms 656 KB Output is correct
5 Correct 623 ms 10064 KB Output is correct
6 Correct 386 ms 692 KB Output is correct
7 Correct 393 ms 656 KB Output is correct
8 Correct 324 ms 780 KB Output is correct
9 Correct 1036 ms 30332 KB Output is correct
10 Correct 1054 ms 30312 KB Output is correct
11 Correct 1930 ms 59836 KB Output is correct
12 Correct 1506 ms 53328 KB Output is correct
13 Correct 335 ms 1000 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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