Submission #469615

#	Time	Username	Problem	Language	Result	Execution time	Memory
469615		jhwest2	Two Transportations (JOI19_transportations)	C++17	6 / 100	752 ms	10212 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;

namespace {

	const int M = 2e3 + 10, INF = 2e9 + 10;
	int n, Dist[M];

	priority_queue<pint, vector<pint>, greater<pint>> Q;
	vector<pint> G[M];

	int cnt = 0, last = 0, bits = 0, type = 0, rnd = 0;
}

void InitA(int N, int a, vector<int> U, vector<int> V, vector<int> C) {
	n = N;
	for (int i = 0; i < n; i++) Dist[i] = INF;
	for (int i = 0; i < a; i++) {
		G[U[i]].emplace_back(C[i], V[i]);
		G[V[i]].emplace_back(C[i], U[i]);
	}
	Dist[0] = 0;
	for (auto [a, b] : G[0]) {
		Q.emplace(a, b);
	}
	if (Q.empty()) {
		for (int i = 0; i < 9; i++) SendA(1);
	}
	else {
		auto [a, b] = Q.top();
		for (int i = 0; i < 9; i++) {
			SendA(a >> i & 1);
		}
	}
	rnd = n - 1;
}

void ReceiveA(bool x) {
	if (type == 0) {
		if (cnt != 8) {
			bits |= x << cnt;
			cnt += 1;
			return;
		}
		bits |= x << cnt;

		
		if (Q.empty() || Q.top().va > last + bits) {
			cnt = 0;
			type = 2;
			last = last + bits;
			bits = 0;
			return;
		}
		
		auto [a, b] = Q.top(); Q.pop();
		
		Dist[b] = a;
		last = Dist[b];
		type = cnt = bits = 0;
		
		
		for (auto [c, d] : G[b]) {
			if (Dist[d] == INF) Q.emplace(last + c, d);
		}
		while (!Q.empty() && Dist[Q.top().vb] != INF) {
			Q.pop();
		}

		int kth = 0;
		for (int i = 0; i < b; i++) {
			if (Dist[i] == INF) kth += 1;
		}
		for (int i = 0; rnd >> i; i++) {
			SendA(kth >> i & 1);			
		}

		rnd -= 1;
		if (rnd == 0) return;

		int d = (Q.empty() ? 511 : Q.top().va - last);
		for (int i = 0; i < 9; i++) {
			SendA(d >> i & 1);
		}
		return;
	}
	if (rnd >> (cnt + 1)) {
		bits |= x << cnt;
		cnt += 1;
		return;
	}
	bits |= x << cnt;

	int kth = 0, b = 0;
	for (int i = 0; i < M; i++) if (Dist[i] == INF) {
		if (kth == bits) {
			b = i; break;
		}
		kth += 1;
	}

	Dist[b] = last;
	type = cnt = bits = 0;
	
	for (auto [c, d] : G[b]) {
		if (Dist[d] == INF) Q.emplace(last + c, d);
	}
	while (!Q.empty() && Dist[Q.top().vb] != INF) {
		Q.pop();
	}

	rnd -= 1;
	if (rnd == 0) return;

	int d = (Q.empty() ? 511 : Q.top().va - last);
	for (int i = 0; i < 9; i++) {
		SendA(d >> i & 1);
	}
}

vector<int> Answer() {
	vector<int> ret;
	for (int i = 0; i < n; i++) {
		ret.push_back(Dist[i]);
	}
	return ret;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;

namespace {

	const int M = 2e3 + 10, INF = 2e9 + 10;
	int n, Dist[M];

	priority_queue<pint, vector<pint>, greater<pint>> Q;
	vector<pint> G[M];

	int cnt = 0, last = 0, bits = 0, type = 0, rnd = 0;
}

void InitB(int N, int b, vector<int> U, vector<int> V, vector<int> C) {
	n = N;
	for (int i = 0; i < n; i++) Dist[i] = INF;
	for (int i = 0; i < b; i++) {
		G[U[i]].emplace_back(C[i], V[i]);
		G[V[i]].emplace_back(C[i], U[i]);
	}
	Dist[0] = 0;
	for (auto [a, b] : G[0]) {
		Q.emplace(a, b);
	}
	if (Q.empty()) {
		for (int i = 0; i < 9; i++) SendB(1);
	}
	else {
		auto [a, b] = Q.top();
		for (int i = 0; i < 9; i++) {
			SendB(a >> i & 1);
		}
	}
	rnd = n - 1;
}

void ReceiveB(bool x) {
	if (type == 0) {
		if (cnt != 8) {
			bits |= x << cnt;
			cnt += 1;
			return;
		}
		bits |= x << cnt;

		
		if (Q.empty() || Q.top().va > last + bits) {
			cnt = 0;
			type = 2;
			last = last + bits;
			bits = 0;
			return;
		}
		
		auto [a, b] = Q.top(); Q.pop();
		
		Dist[b] = a;
		last = Dist[b];
		type = cnt = bits = 0;
		
		
		for (auto [c, d] : G[b]) {
			if (Dist[d] == INF) Q.emplace(last + c, d);
		}
		while (!Q.empty() && Dist[Q.top().vb] != INF) {
			Q.pop();
		}

		int kth = 0;
		for (int i = 0; i < b; i++) {
			if (Dist[i] == INF) kth += 1;
		}
		for (int i = 0; rnd >> i; i++) {
			SendB(kth >> i & 1);			
		}

		rnd -= 1;
		if (rnd == 0) return;
		
		int d = (Q.empty() ? 511 : Q.top().va - last);
		for (int i = 0; i < 9; i++) {
			SendB(d >> i & 1);
		}
		return;
	}
	if (rnd >> (cnt + 1)) {
		bits |= x << cnt;
		cnt += 1;
		return;
	}
	bits |= x << cnt;

	int kth = 0, b = 0;
	for (int i = 0; i < M; i++) if (Dist[i] == INF) {
		if (kth == bits) {
			b = i; break;
		}
		kth += 1;
	}

	Dist[b] = last;
	type = cnt = bits = 0;
	
	for (auto [c, d] : G[b]) {
		if (Dist[d] == INF) Q.emplace(last + c, d);
	}
	while (!Q.empty() && Dist[Q.top().vb] != INF) {
		Q.pop();
	}

	rnd -= 1;
	if (rnd == 0) return;

	int d = (Q.empty() ? 511 : Q.top().va - last);
	for (int i = 0; i < 9; i++) {
		SendB(d >> i & 1);
	}
}

• Subtask 1: 6 / 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