Submission #123540

#	Time	Username	Problem	Language	Result	Execution time	Memory
123540		youngyojun	Two Transportations (JOI19_transportations)	C++14	8 / 100	3000 ms	25956 KiB

Azer

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

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 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 i = 0; i < N; i++) if(chk[i]) {
		for(int e : G[i]) {
			int v = A[e]^B[e]^i;
			int d = D[i] + C[e];
			if(d < D[v]) D[v] = d;
		}
	}
	int hc = MAXC*N+1;
	for(int i = 0; i < N; i++)
		if(!chk[i] && D[i] < hc) {
			hc = D[i];
			mnV = i;
		}
}

static void spread(int sidx, int sdst) {
	chk[sidx] = true; K++;
	LV.eb(sidx); D[sidx] = sdst;
	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);
	D[0] = 0; chk[0] = true;
	LV.eb(0); K = 1;

	calMin();
}

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;

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 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 i = 0; i < N; i++) if(chk[i]) {
		for(int e : G[i]) {
			int v = A[e]^B[e]^i;
			int d = D[i] + C[e];
			if(d < D[v]) D[v] = d;
		}
	}
	int hc = MAXC*N+1;
	for(int i = 0; i < N; i++)
		if(!chk[i] && D[i] < hc) {
			hc = D[i];
			mnV = i;
		}
	sendInt(min(MAXC+1, D[mnV] - D[LV.back()]), MAXLGC);
}

static void spread(int sidx, int sdst) {
	chk[sidx] = true; K++;
	LV.eb(sidx); D[sidx] = sdst;
	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);
	D[0] = 0; chk[0] = true;
	LV.eb(0); K = 1;

	calMin();
}

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: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 8 / 8
• Subtask 4: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16