Submission #1244962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244962		Tob	Two Transportations (JOI19_transportations)	C++20	100 / 100	354 ms	49056 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

static const int N = 2007, mxc = (1 << 9)-1, inf = 1e9;
static int n, m, ldis, str, x, y, w, ncnt;
static set <pii> s;
static vector <pii> adj[N];
static vector <int> d;
static queue <int> bits;

void InitA(int nn, int aa, vector<int> uu, vector<int> vv, vector<int> cc) {
	n = nn; m = aa;
	for (int i = 0; i < m; i++) {
		adj[uu[i]].pb({vv[i], cc[i]});
		adj[vv[i]].pb({uu[i], cc[i]});
	}
	str = -1;
	ncnt = n-1;
	d.resize(n, inf);
	d[0] = 0;
	for (auto it : adj[0]) d[it.F] = it.S;
	for (int i = 1; i < n; i++) s.insert({d[i], i});
}

void ReceiveA(bool bit) {
	for (int _ = 0; _ < 2; _++) {
		
	if (str != -1) bits.push(bit);
	else str = 0;
	
	auto snum = [&](int xx, int si) {
		for (int i = 0; i < si; i++) SendA((xx>>i)&1);
	};
	
	auto rnum = [&](int si) {
		int xx = 0;
		for (int i = 0; i < si; i++) {
			xx |= (int)bits.front() << i;
			bits.pop();
		}
		return xx;
	};
	
	if (str == 1 && bits.size() < 9) return;
	if (str == 2 && bits.size() < 11) return;
	
	
	if (!str) {
		y = n, w = mxc;
		for (auto it : s) {
			if (it.F-ldis < w) {
				w = it.F-ldis;
				y = it.S;
			}
		}
		snum(w, 9);
//		cout << "A sends " << w << "\n";
		str = 1;
		return;
	}
	else if (str == 1) {
		x = rnum(9);
//		cout << "A recieves " << x << "\n";
		if (x > w) snum(y, 11);//, cout << "A sends " << y << "\n";
		else {
			str = 2;
			return;
		}
	}
	else {
		y = rnum(11);
		w = x;
//		cout << "A recievese " << y << "\n";
	}
	
//	cout << d[y] << " " << ldis << " " << w << "\n";
	s.erase({d[y], y});
	d[y] = (ldis += w);
	for (auto it : adj[y]) {
		if (d[y]+it.S < d[it.F]) {
			s.erase({d[it.F], it.F});
			d[it.F] = d[y]+it.S;
			s.insert({d[it.F], it.F});
		}
	}
	str = -1;
	ncnt--;
	if(!ncnt) return;
	}
//	cout << ldis << "\n";
//	for (auto it : d) cout << it << " "; cout << "\n";
}

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

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

static const int N = 2007, mxc = (1 << 9)-1, inf = 1e9;
static int n, m, ldis, str, x, y, w;
static set <pii> s;
static vector <pii> adj[N];
static vector <int> d;
static queue <int> bits;

void InitB(int nn, int bb, vector<int> ss, vector<int> tt, vector<int> dd) {
	n = nn; m = bb;
	for (int i = 0; i < m; i++) {
		adj[ss[i]].pb({tt[i], dd[i]});
		adj[tt[i]].pb({ss[i], dd[i]});
	}
	d.resize(n, inf);
	d[0] = 0;
	for (auto it : adj[0]) d[it.F] = it.S;
	for (int i = 1; i < n; i++) s.insert({d[i], i});
	str = 0;
	if (n > 1) SendB(1);
}

void ReceiveB(bool bit) {
	bits.push(bit);
//	cout << "B" << bit << "\n";
	
	auto snum = [&](int xx, int si) {
		for (int i = 0; i < si; i++) SendB((xx>>i)&1);
	};
	
	auto rnum = [&](int si) {
		int xx = 0;
		for (int i = 0; i < si; i++) {
			xx |= (int)bits.front() << i;
			bits.pop();
		}
		return xx;
	};
	
	if (!str && bits.size() < 9) return;
	if (str && bits.size() < 11) return;
	
	if (!str) {
		y = n, w = mxc;
		for (auto it : s) {
			if (it.F-ldis < w) {
				w = it.F-ldis;
				y = it.S;
			}
		}
		x = rnum(9);
//		cout << "B recieves " << x << "\n";
		if (x >= w) {
			snum(w, 9);
			snum(y, 11);
//			cout << "B sends " << w << " " << y << "\n";
		}
		else {
			snum(w, 9);
//			cout << "B sends " << w << "\n";
			str = 1;
			return;
		}
	}
	else {
		y = rnum(11);
		w = x;
//		cout << "B recieves " << y << "\n";
	}
	
	s.erase({d[y], y});
	d[y] = (ldis += w);
	for (auto it : adj[y]) {
		if (d[y]+it.S < d[it.F]) {
			s.erase({d[it.F], it.F});
			d[it.F] = d[y]+it.S;
			s.insert({d[it.F], it.F});
		}
	}
	str = 0;
}

• 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