Submission #266610

#	Time	Username	Problem	Language	Result	Execution time	Memory
266610		dolphingarlic	Two Transportations (JOI19_transportations)	C++14	100 / 100	2450 ms	113344 KiB

Azer

#include "Azer.h"

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

namespace {
int N, stage = 0, cnt, b_shortest, mx_so_far;
vector<pair<int, int>> graph[2000];
vector<int> shortest;
priority_queue<pair<int, int>> pq;
bool visited[2000];
pair<int, int> cand = {0, 0};

void reset() {
	visited[cand.second] = true;
	shortest[cand.second] = cand.first;
	mx_so_far = cand.first;
	for (pair<int, int> i : graph[cand.second])
		pq.push({-cand.first - i.second, i.first});
	N--;

	if (!N) return;

	while (pq.size() && visited[pq.top().second]) pq.pop();
	if (pq.size()) cand = {-pq.top().first, pq.top().second};
	else cand = {mx_so_far + 511, -1};

	for (int i = 0; i < 9; i++) SendA(((cand.first - mx_so_far) & (1 << i)) >> i);
	cnt = stage = b_shortest = 0;
}
}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
	::N = N;
	shortest.resize(N);
	for (int i = 0; i < A; i++) {
		graph[U[i]].push_back({V[i], C[i]});
		graph[V[i]].push_back({U[i], C[i]});
	}
	reset();
}

void ReceiveA(bool x) {
	if (stage == 0) {
		b_shortest |= x << cnt++;
		if (cnt == 9) {
			if (b_shortest == 511) {
				for (int i = 0; i < 11; i++) SendA((cand.second & (1 << i)) >> i);
				reset();
			} else {
				stage++;
				cand = {mx_so_far + b_shortest, 0};
				cnt = 0;
			}
		}
	} else {
		cand.second |= x << cnt++;
		if (cnt == 11) reset();
	}
}

vector<int> Answer() {
	return shortest;
}

Baijan

#include "Baijan.h"

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

namespace {
int N, stage = 0, cnt, a_shortest, mx_so_far;
vector<pair<int, int>> graph[2000];
vector<int> shortest;
priority_queue<pair<int, int>> pq;
bool visited[2000];
pair<int, int> cand = {0, 0};

void reset() {
	visited[cand.second] = true;
	shortest[cand.second] = cand.first;
	mx_so_far = cand.first;
	for (pair<int, int> i : graph[cand.second])
		pq.push({-cand.first - i.second, i.first});

	while (pq.size() && visited[pq.top().second]) pq.pop();
	if (pq.size()) cand = {-pq.top().first, pq.top().second};
	else cand = {mx_so_far + 511, -1};

	cnt = stage = a_shortest = 0;
}
}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
	::N = N;
	shortest.resize(N);
	for (int i = 0; i < B; i++) {
		graph[S[i]].push_back({T[i], D[i]});
		graph[T[i]].push_back({S[i], D[i]});
	}
	reset();
}

void ReceiveB(bool y) {
	if (stage == 0) {
		a_shortest |= y << cnt++;
		if (cnt == 9) {
			if (a_shortest > cand.first - mx_so_far) {
				for (int i = 0; i < 9; i++) SendB(((cand.first - mx_so_far) & (1 << i)) >> i);
				for (int i = 0; i < 11; i++) SendB((cand.second & (1 << i)) >> i);
				reset();
			} else {
				for (int i = 0; i < 9; i++) SendB(1);
				cnt = 0;
				cand = {a_shortest + mx_so_far, 0};
				stage++;
			}
		}
	} else if (stage == 1) {
		cand.second |= y << cnt++;
		if (cnt == 11) reset();
	}
}

• 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