제출 #1237890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237890		box	Two Transportations (JOI19_transportations)	C++20	0 / 100	153 ms	1096 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
typedef array<int, 2> ar2;
typedef vector<int> vi;

namespace {
const int N = 2000, A = 500, INF = N*A;
mt19937 rng(19260817);
int n;
int d[N];
bool marked[N];
vector<ar2> adj[N];
vector<bool> bits;
int last_d, i;
int state;
// 0: sent distance, waiting for response
// 1: got 1, waiting for distance and index
// 2: waiting for distance
// 3: sent 0, waiting for index

void spread(int i) {
	marked[i] = true;
	for (auto [j, c] : adj[i])
		d[j] = min(d[j], d[i]+c);
	last_d = d[i];
}
void init() {
	i = -1;
	for (int j = 0; j < n; j++) if (!marked[j] && (i == -1 || d[j] < d[i]))
		i = j;
	if (i == -1) return;

	if (rng()%2 == 0) {
		int v = min(A+1, d[i]-last_d);
		for (int j = 0; j < 8; j++) SendA(v>>j&1);
		state = 0;
	} else {
		state = 2;
	}
}
void process(bool b) {
	bits.push_back(b);
	if (state == 0) {
		assert(sz(bits) == 1);
		if (bits[0] == 1) {
			bits.clear();
			state = 1;
		} else {
			bits.clear();
			for (int j = 0; j < 11; j++) SendA(i>>j&1);
			spread(i);
			init();
		}
	} else if (state == 1) {
		if (sz(bits) == 8+11) {
			int v = 0;
			for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
			i = 0;
			for (int j = 0; j < 11; j++) i += int(bits[8+j])<<j;
			bits.clear();
			d[i] = last_d+v;
			init();
		}
	} else if (state == 2) {
		if (sz(bits) == 8) {
			int v = 0;
			for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
			bits.clear();
			if (d[i]-last_d < v) {
				SendA(1);
				v = d[i]-last_d;
				for (int j = 0; j < 8; j++) SendA(v>>j&1);
				for (int j = 0; j < 11; j++) SendA(i>>j&1);
				spread(i);
				init();
			} else {
				state = 3, last_d += v;
				SendA(0);
			}
		}
	} else if (state == 3) {
		if (sz(bits) == 11) {
			i = 0;
			for (int j = 0; j < 11; j++) i += int(bits[j])<<j;
			bits.clear();
			d[i] = last_d;
			spread(i);
			init();
		}
	}
}
}

void InitA(int n, int a, vi u, vi v, vi c) {
	::n = n;
	for (int i = 0; i < a; i++) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	fill(marked, marked+n, false);
	fill(d, d+n, INF);
	d[0] = 0;
	spread(0);
	init();
}

void ReceiveA(bool x) {
	process(x);
}

vi Answer() {
	return vi(d, d+n);
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
typedef array<int, 2> ar2;
typedef vector<int> vi;

namespace {
const int N = 2000, A = 500, INF = N*A;
mt19937 rng(19260817);
int n;
int d[N];
bool marked[N];
vector<ar2> adj[N];
vector<bool> bits;
int last_d, i;
int state;
// 0: sent distance, waiting for response
// 1: got 1, waiting for distance and index
// 2: waiting for distance
// 3: sent 0, waiting for index

void spread(int i) {
	marked[i] = true;
	for (auto [j, c] : adj[i])
		d[j] = min(d[j], d[i]+c);
	last_d = d[i];
}
void init() {
	i = -1;
	for (int j = 0; j < n; j++) if (!marked[j] && (i == -1 || d[j] < d[i]))
		i = j;
	if (i == -1) return;

	if (rng()%2 == 1) {
		int v = min(A+1, d[i]-last_d);
		for (int j = 0; j < 8; j++) SendB(v>>j&1);
		state = 0;
	} else {
		state = 2;
	}
}
void process(bool b) {
	bits.push_back(b);
	if (state == 0) {
		assert(sz(bits) == 1);
		if (bits[0] == 1) {
			bits.clear();
			state = 1;
		} else {
			bits.clear();
			for (int j = 0; j < 11; j++) SendB(i>>j&1);
			spread(i);
			init();
		}
	} else if (state == 1) {
		if (sz(bits) == 8+11) {
			int v = 0;
			for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
			i = 0;
			for (int j = 0; j < 11; j++) i += int(bits[8+j])<<j;
			bits.clear();
			d[i] = last_d+v;
			init();
		}
	} else if (state == 2) {
		if (sz(bits) == 8) {
			int v = 0;
			for (int j = 0; j < 8; j++) v += int(bits[j])<<j;
			bits.clear();
			if (d[i]-last_d < v) {
				SendB(1);
				v = d[i]-last_d;
				for (int j = 0; j < 8; j++) SendB(v>>j&1);
				for (int j = 0; j < 11; j++) SendB(i>>j&1);
				spread(i);
				init();
			} else {
				state = 3, last_d += v;
				SendB(0);
			}
		}
	} else if (state == 3) {
		if (sz(bits) == 11) {
			i = 0;
			for (int j = 0; j < 11; j++) i += int(bits[j])<<j;
			bits.clear();
			d[i] = last_d;
			spread(i);
			init();
		}
	}
}
}

void InitB(int n, int a, vi u, vi v, vi c) {
	::n = n;
	for (int i = 0; i < a; i++) {
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	fill(marked, marked+n, false);
	fill(d, d+n, INF);
	d[0] = 0;
	spread(0);
	init();
}

void ReceiveB(bool x) {
	process(x);
}

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