oj.uz

답안 #123540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123540 2019-07-01T14:53:23 Z youngyojun Two Transportations (JOI19_transportations) C++14
8 / 100
 3000 ms 25956 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+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;
}
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1174 ms 1608 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 1238 ms 1768 KB Output is correct
4 Execution timed out 3000 ms 10348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1248 KB Output is correct
2 Correct 1306 ms 1760 KB Output is correct
3 Correct 1440 ms 2352 KB Output is correct
4 Execution timed out 3000 ms 25956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1256 ms 1944 KB Output is correct
2 Correct 4 ms 1240 KB Output is correct
3 Correct 1286 ms 1728 KB Output is correct
4 Correct 1060 ms 1952 KB Output is correct
5 Correct 1236 ms 1768 KB Output is correct
6 Correct 1106 ms 1872 KB Output is correct
7 Correct 1150 ms 1768 KB Output is correct
8 Correct 1120 ms 1584 KB Output is correct
9 Correct 1190 ms 1816 KB Output is correct
10 Correct 1416 ms 1792 KB Output is correct

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 1720 KB Output is correct
2 Correct 536 ms 1760 KB Output is correct
3 Execution timed out 3000 ms 22264 KB
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 1720 KB Output is correct
2 Correct 536 ms 1760 KB Output is correct
3 Execution timed out 3000 ms 22264 KB
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 583 ms 1720 KB Output is correct
2 Correct 536 ms 1760 KB Output is correct
3 Execution timed out 3000 ms 22264 KB
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1174 ms 1608 KB Output is correct
2 Correct 6 ms 1232 KB Output is correct
3 Correct 1238 ms 1768 KB Output is correct
4 Execution timed out 3000 ms 10348 KB Time limit exceeded
5 Halted 0 ms 0 KB -