Submission #130126

#	Time	Username	Problem	Language	Result	Execution time	Memory
130126		tjd229	Two Transportations (JOI19_transportations)	C++14	100 / 100	1924 ms	85320 KiB

Azer

#include "Azer.h"
#include <vector>
#include <queue>
#define pii std::pair<int,int>
#define vec std::vector<pii >
#define pq std::priority_queue<pii >
namespace {

int N;
int vis[2000];
vec edge[2000];
int d[2000];
int buf[20];
int sz, r;
pq q;
int recon() {
	int n = 0;
	for (int i = 0; i < sz; ++i) 
		n += n + buf[i];
	return n;
}
}  // namespace
void _SendA(int n,int k) {
	while (k--) {
		SendA(n&1);
		n >>= 1;
	}
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
	::N = N;
	for (int i = 0; i < A; ++i) {
		edge[U[i]].push_back({V[i],C[i]});
		edge[V[i]].push_back({ U[i],C[i] });
	}
	for (int i = 0; i < N; ++i) q.push({ -1e9,i }), d[i] = 1e9;
	vis[0] = 1; d[0] = 0;
	for (auto p : edge[0]) {
		int v = p.first;
		int c = p.second;
		d[v] = c;
		q.push({-d[v],v});
	}
	int da=-q.top().first;
	if (da > 500) da = 510;
	_SendA(da, 9); sz = r = 9;
	buf[18] = 0;
}

void ReceiveA(bool x) {
	buf[--r]=x;
	if (r == 0) {
		int v;
		if (sz == 9) {
			int db = recon();
			v = q.top().second;
			int da = d[v] - d[buf[18]];
			if (da <= db) {
				_SendA(v,11);
				q.pop();
				//go inq
			}
			else {
				buf[19] = db;
				r = sz = 11;
				return;
			}
		}
		else {//sync v
			v= recon();
			d[v] = d[buf[18]] + buf[19];
			//go inq
		}
		//inq
		vis[v] = 1;
		for (auto p : edge[v]) {
			int nxt = p.first;
			int c = p.second;
			if (d[nxt] > d[v] + c) {
				d[nxt] = d[v] + c;
				q.push({ -d[nxt],nxt });
			}
		}
		while (q.size() && vis[q.top().second]) q.pop();//q empty chk??
		if (q.size()) {
			int da = -q.top().first;
			int diff = da - d[v];
			if (diff > 500) diff = 510;
			_SendA(diff, 9);
			r = sz = 9;
			buf[18] = v;
		}
	}
}

std::vector<int> Answer() {
  std::vector<int> ans(N);
  for (int i = 0; i < N; ++i) ans[i] = d[i];
  return ans;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <queue>
#define pii std::pair<int,int>
#define vec std::vector<pii >
#define pq std::priority_queue<pii >

namespace {
	int N;
	int vis[2000];
	vec edge[2000];
	int d[2000];
	int sz, r;
	int buf[20];
	pq q;
	int recon() {
		int n = 0;
		for (int i = 0; i < sz; ++i) n += n + buf[i];
		return n;
	}
}  // namespace
void _SendB(int n, int k) {
	while (k--) {
		SendB(n & 1);
		n >>= 1;
	}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
	::N = N;
	for (int i = 0; i < B; ++i) {
		edge[S[i]].push_back({T[i],D[i]});
		edge[T[i]].push_back({ S[i],D[i] });
	}
	for (int i = 0; i < N; ++i) q.push({ -1e9,i }), d[i] = 1e9;
	vis[0] = 1; d[0] = 0;
	for (auto p : edge[0]) {
		int v = p.first;
		int c = p.second;
		d[v] = c;
		q.push({ -d[v],v });
	}
	int db = -q.top().first;
	if (db > 500) db = 510;
	_SendB(db, 9); sz = r = 9; buf[18] = 0;
}

void ReceiveB(bool y) {
	buf[--r] = y;
	if (r == 0) {
		int v;
		if (sz == 9) {
			int da = recon();
			v = q.top().second;
			int db = d[v]-d[buf[18]];
			if (da > db) {
				_SendB(v, 11);
				q.pop();
				//go inq
			}
			else {
				buf[19] = da;
				r = sz = 11;
				return;
			}
		}
		else {//sync v
			v = recon();
			d[v] = d[buf[18]] + buf[19];
			//go inq
		}
		//inq
		vis[v] = 1;
		for (auto p : edge[v]) {
			int nxt = p.first;
			int c = p.second;
			if (d[nxt] > d[v] + c) {
				d[nxt] = d[v] + c;
				q.push({ -d[nxt],nxt });
			}
		}
		while (q.size() && vis[q.top().second]) q.pop();//q empty chk??
		if (q.size()) {
			int db = -q.top().first;
			int diff = db - d[v];
			if (diff > 500) diff = 510;
			_SendB(diff, 9);
			r = sz = 9;
			buf[18] = v;
		}
	}
}

• 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