oj.uz

Submission #123538

# Submission time Handle Problem Language Result Execution time Memory
123538 2019-07-01T14:38:01 Z youngyojun Two Transportations (JOI19_transportations) C++14
0 / 100
 1288 ms 2016 KB 
#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;
	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;
}
#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;
	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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1086 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1256 KB Output is correct
2 Incorrect 920 ms 1728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1288 ms 2016 KB Output is correct
2 Correct 4 ms 1248 KB Output is correct
3 Incorrect 1018 ms 1600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 1720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 1720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 1720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1086 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -