Submission #123542

#	Time	Username	Problem	Language	Result	Execution time	Memory
123542		youngyojun	Two Transportations (JOI19_transportations)	C++14	100 / 100	2614 ms	84432 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
using namespace std;
typedef pair<int, int> pii;

static const int MAXN = 2000;
static const int MAXM = 500000;
static const int MAXC = 500;
static const int MAXLGN = 11;
static const int MAXLGC = 9;

static queue<bool> BTQ;

static priority_queue<pii, vector<pii>, greater<pii>> PQ;
static int D[MAXN];
static vector<int> LV;
static bitset<MAXN> chk;

static vector<int> G[MAXN];
static int A[MAXM], B[MAXM], C[MAXM];

static int N, M, K, mnV;

static void send(bool x) { SendA(x); }
static void sendInt(int x, int l) {
	for(int i = 0; i < l; i++)
		send(x & (1<<i));
}
static int getInt(int l) {
	int r = 0;
	for(int i = 0; i < l; i++) {
		if(BTQ.front()) r |= 1 << i;
		BTQ.pop();
	}
	return r;
}

static void calMin() {
	for(int idx, dst; !PQ.empty();) {
		tie(dst, idx) = PQ.top();
		if(!chk[idx]) break;
		PQ.pop();
		for(int e : G[idx]) {
			int v = A[e]^B[e]^idx;
			int d = D[idx] + C[e];
			if(D[v] <= d) continue;
			D[v] = d;
			PQ.push({d, v});
		}
	}
	mnV = PQ.top().second;
}

static void spread(int idx, int dst) {
	chk[idx] = true; K++;
	LV.eb(idx); D[idx] = dst;
	PQ.push({dst, idx});
	if(K < N) calMin();
}

static void init() {
	if(1 == N) return;
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	fill(D, D+N, MAXC*N);
	for(int i = 0; i < N; i++) PQ.push({D[i], i});
	spread(0, 0);
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	::N = N; ::M = A;
	for(int i = 0; i < ::M; i++) {
		::A[i] = U[i];
		::B[i] = V[i];
		::C[i] = C[i];
	}
	init();
}

static int readyDist;
static bool isReady;
void ReceiveA(bool x) {
	if(K == N) return;
	BTQ.push(x);
	if(!isReady) {
		if(sz(BTQ) < MAXLGC) return;
		readyDist = D[LV.back()] + getInt(MAXLGC);
		if(D[mnV] <= readyDist) {
			sendInt(D[mnV] - D[LV.back()], MAXLGC);
			sendInt(mnV, MAXLGN);
			spread(mnV, D[mnV]);
			return;
		}
		sendInt(MAXC+1, MAXLGC);
		isReady = true;
	} else {
		if(sz(BTQ) < MAXLGN) return;
		spread(getInt(MAXLGN), readyDist);
		isReady = false;
	}
}

std::vector<int> Answer() {
	vector<int> V;
	for(int i = 0; i < N; i++) V.eb(D[i]);
	return V;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
using namespace std;
typedef pair<int, int> pii;

static const int MAXN = 2000;
static const int MAXM = 500000;
static const int MAXC = 500;
static const int MAXLGN = 11;
static const int MAXLGC = 9;

static queue<bool> BTQ;

static priority_queue<pii, vector<pii>, greater<pii>> PQ;
static int D[MAXN];
static vector<int> LV;
static bitset<MAXN> chk;

static vector<int> G[MAXN];
static int A[MAXM], B[MAXM], C[MAXM];

static int N, M, K, mnV;

static void send(bool x) { SendB(x); }
static void sendInt(int x, int l) {
	for(int i = 0; i < l; i++)
		send(x & (1<<i));
}
static int getInt(int l) {
	int r = 0;
	for(int i = 0; i < l; i++) {
		if(BTQ.front()) r |= 1 << i;
		BTQ.pop();
	}
	return r;
}

static void calMin() {
	for(int idx, dst; !PQ.empty();) {
		tie(dst, idx) = PQ.top();
		if(!chk[idx]) break;
		PQ.pop();
		for(int e : G[idx]) {
			int v = A[e]^B[e]^idx;
			int d = D[idx] + C[e];
			if(D[v] <= d) continue;
			D[v] = d;
			PQ.push({d, v});
		}
	}
	mnV = PQ.top().second;
	sendInt(min(MAXC+1, D[mnV] - D[LV.back()]), MAXLGC);
}

static void spread(int idx, int dst) {
	chk[idx] = true; K++;
	LV.eb(idx); D[idx] = dst;
	PQ.push({dst, idx});
	if(K < N) calMin();
}

static void init() {
	if(1 == N) return;
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	fill(D, D+N, MAXC*N);
	for(int i = 0; i < N; i++) PQ.push({D[i], i});
	spread(0, 0);
}

void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	::N = N; ::M = A;
	for(int i = 0; i < ::M; i++) {
		::A[i] = U[i];
		::B[i] = V[i];
		::C[i] = C[i];
	}
	init();
}

static int readyDist;
static bool isReady;
void ReceiveB(bool x) {
	if(K == N) return;
	BTQ.push(x);
	if(!isReady) {
		if(sz(BTQ) < MAXLGC) return;
		readyDist = getInt(MAXLGC);
		if(MAXC < readyDist) {
			sendInt(mnV, MAXLGN);
			spread(mnV, D[mnV]);
			return;
		}
		readyDist += D[LV.back()];
		isReady = true;
	} else {
		if(sz(BTQ) < MAXLGN) return;
		spread(getInt(MAXLGN), readyDist);
		isReady = false;
	}
}

• 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