Submission #670496

#	Time	Username	Problem	Language	Result	Execution time	Memory
670496		ymm	Two Transportations (JOI19_transportations)	C++17	100 / 100	929 ms	48808 KiB

Azer

#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(int v);

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

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(s.begin()->second);
	}
}

void dij(int v)
{
	int d = dis[v];
	s.erase({dis[v], v});
	cerr << "A with " << v << " dis " << d << '\n';
	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(0);
}

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;
}

Baijan

#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(int v);

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

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(s.begin()->second);
	}
}

void dij(int v)
{
	int d = dis[v];
	s.erase({dis[v], v});
	cerr << "B with " << v << " dis " << d << '\n';
	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(0);
}

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

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16