oj.uz

답안 #670493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670493 2022-12-09T09:33:06 Z ymm Two Transportations (JOI19_transportations) C++17
6 / 100
 747 ms 27892 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace {

const int N = 2048;
const int inf = 1e9;
vector<pii> A[N];
int dis[N];
set<pii> s;
int rem;
int n;

int want;
void (*want_func)();
queue<bool> q;
int lst_d;
int recv_up_d;

}  // namespace

namespace {

void send(int x, int b)
{
	cerr << "A send " << x << '\n';
	while (b--) {
		SendA(x & 1);
		x /= 2;
	}
}

int recv(int b)
{
	int ans = 0;
	Loop (i,0,b) {
		ans ^= (int)q.front() << i;
		q.pop();
	}
	cerr << "A recv " << ans << '\n';
	return ans;
}

void up(int v, int d)
{
	if (d >= dis[v])
		return;
	s.erase({dis[v], v});
	dis[v] = d;
	s.insert({dis[v], v});
}

void recv_up();
void cmp();
void dij();

void recv_up()
{
	int v = recv(11);
	up(v, recv_up_d);
	dij();
}

int get_nxt()
{
	return s.size()? s.begin()->first: 511 + lst_d;
}

void cmp()
{
	int self = get_nxt();
	int other = recv(9) + lst_d;
	if (self > other) {
		want = 11;
		want_func = recv_up;
		recv_up_d = other;
	} else {
		assert(s.size());
		send(s.begin()->second, 11);
		dij();
	}
}

void dij()
{
	assert(s.size());
	auto [d, v] = *s.begin();
	cerr << "A with " << v << " dis " << d << '\n';
	s.erase(s.begin());
	for (auto [u, w] : A[v])
		up(u, d+w);
	lst_d = d;
	--rem;
	if (!rem)
		return;
	send(get_nxt() - lst_d, 9);
	want = 9;
	want_func = cmp;
}

}

void InitA(int _n, int m, std::vector<int> V, std::vector<int> U,
           std::vector<int> W)
{
	n = _n;
	rem = n;
	Loop (i,0,m) {
		int v = V[i], u = U[i], w = W[i];
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	fill(dis, dis+n, inf);
	up(0, 0);
	dij();
}

void ReceiveA(bool x)
{
	q.push(x);
	--want;
	if (!want) {
		want_func();
	}
}

std::vector<int> Answer()
{
	vector<int> ans(n);
	Loop (i,0,n)
		ans[i] = dis[i];
	return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

namespace {

const int N = 2048;
const int inf = 1e9;
vector<pii> A[N];
int dis[N];
set<pii> s;
int rem;
int n;

int want;
void (*want_func)();
queue<bool> q;
int lst_d;
int recv_up_d;

}  // namespace

namespace {

void send(int x, int b)
{
	cerr << "B send " << x << '\n';
	while (b--) {
		SendB(x & 1);
		x /= 2;
	}
}

int recv(int b)
{
	int ans = 0;
	Loop (i,0,b) {
		ans ^= (int)q.front() << i;
		q.pop();
	}
	cerr << "B recv " << ans << '\n';
	return ans;
}

void up(int v, int d)
{
	if (d >= dis[v])
		return;
	s.erase({dis[v], v});
	dis[v] = d;
	s.insert({dis[v], v});
}

void recv_up();
void cmp();
void dij();

void recv_up()
{
	int v = recv(11);
	up(v, recv_up_d);
	dij();
}

int get_nxt()
{
	return s.size()? s.begin()->first: 511 + lst_d;
}

void cmp()
{
	int self = get_nxt();
	int other = recv(9) + lst_d;
	if (self >= other) {
		want = 11;
		want_func = recv_up;
		recv_up_d = other;
	} else {
		assert(s.size());
		send(s.begin()->second, 11);
		dij();
	}
}

void dij()
{
	assert(s.size());
	auto [d, v] = *s.begin();
	cerr << "B with " << v << " dis " << d << '\n';
	s.erase(s.begin());
	for (auto [u, w] : A[v])
		up(u, d+w);
	lst_d = d;
	--rem;
	if (!rem)
		return;
	send(get_nxt() - lst_d, 9);
	want = 9;
	want_func = cmp;
}

}

void InitB(int _n, int m, std::vector<int> V, std::vector<int> U,
           std::vector<int> W)
{
	n = _n;
	rem = n;
	Loop (i,0,m) {
		int v = V[i], u = U[i], w = W[i];
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	fill(dis, dis+n, inf);
	up(0, 0);
	dij();
}

void ReceiveB(bool x)
{
	q.push(x);
	--want;
	if (!want) {
		want_func();
	}
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 497 ms 1144 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 575 ms 1220 KB Output is correct
4 Correct 513 ms 10320 KB Output is correct
5 Correct 37 ms 912 KB Output is correct
6 Correct 562 ms 2408 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 552 ms 1232 KB Output is correct
3 Correct 603 ms 1220 KB Output is correct
4 Correct 705 ms 27892 KB Output is correct
5 Correct 747 ms 24380 KB Output is correct
6 Correct 120 ms 736 KB Output is correct
7 Incorrect 735 ms 24708 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 497 ms 1144 KB Output is correct
2 Correct 1 ms 656 KB Output is correct
3 Correct 575 ms 1220 KB Output is correct
4 Correct 513 ms 10320 KB Output is correct
5 Correct 37 ms 912 KB Output is correct
6 Correct 562 ms 2408 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 552 ms 1232 KB Output is correct
9 Correct 603 ms 1220 KB Output is correct
10 Correct 705 ms 27892 KB Output is correct
11 Correct 747 ms 24380 KB Output is correct
12 Correct 120 ms 736 KB Output is correct
13 Incorrect 735 ms 24708 KB Output isn't correct
14 Halted 0 ms 0 KB -