oj.uz

Submission #123333

# Submission time Handle Problem Language Result Execution time Memory
123333 2019-07-01T07:29:55 Z 윤교준(#3020) Two Transportations (JOI19_transportations) C++14
0 / 100
 125 ms 1264 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

static const int MAXN = 1400;
static const int MAXM = 500000;
static const int MAXL = (MAXN-1) * 500;
static const int MAXLGL = 20;

static queue<bool> RQB;
static int needBits[MAXN+1];

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

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

static int N, M, K;

static void send(bool x) { SendA(x); }
static void sendVertex(int v) {
	//int l = needBits[K+1];
	int l = needBits[N];
	for(int i = 0; i < l; i++) send(v & (1<<l));
}
static void sendInt(int x) {
	int l = MAXLGL;
	for(int i = 0; i < l; i++) send(x & (1<<i));
}
static int getInt(int l) {
	int ret = 0;
	for(int i = 0; i < l; i++) {
		if(RQB.front()) ret |= 1 << i;
		RQB.pop();
	}
	return ret;
}
static int getVertex() { return getInt(needBits[N]); }
static int getInt() { return getInt(MAXLGL); }


static int getMinDist() {
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	return PQ.empty() ? MAXL : PQ.top().first;
}

static void sendInfo() {
	if(K == N) return;
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	if(PQ.empty()) {
		sendVertex(0);
		return;
	}
	int dst, idx;
	tie(dst, idx) = PQ.top();
	sendVertex(idx);
	sendInt(dst);
}

static void spread(int sidx, int sdst) {
	if(K == N) return;
	if(!chk[sidx]) {
		chk[sidx] = true;
		DP[sidx] = sdst;
		K++;
		PQ.push({sidx, sdst});
		for(int idx, dst; !PQ.empty();) {
			tie(dst, idx) = PQ.top();
			if(!chk[idx]) break;
			PQ.pop();
			if(DP[idx] < dst) continue;
			for(int e : G[idx]) {
				int v = A[e]^B[e]^idx;
				int ndst = dst + C[e];
				if(DP[v] <= ndst) continue;
				DP[v] = ndst;
				PQ.push({ndst, v});
			}
		}
	}
	sendInfo();
}
static void spreadTop() {
	if(K == N) return;
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	spread(PQ.top().second, PQ.top().first);
}


static void init() {
	for(int i = 0, s, e;; i++) {
		s = 1<<i; e = s<<1;
		if(MAXN < s) break;
		for(int j = s; j < e && j <= MAXN; j++)
			needBits[j] = i;
	}
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}

	fill(DP, DP+N, MAXL);
	spread(0, 0);
}

static bool stayForLen = false;
static int stayIndex;
void ReceiveA(bool x) {
	RQB.push(x);

	if(stayForLen) {
		int l = MAXLGL;
		if(sz(RQB) < l) return;
		int dst = getInt();
		if(getMinDist() < l) {
			spreadTop();
			return;
		}
		spread(l, dst);
		return;
	}

	int l = needBits[N];
	if(sz(RQB) == l) {
		int v = getVertex();
		if(!v) {
			spreadTop();
		} else {
			stayForLen = true;
			stayIndex = v;
		}
	}
}

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();
}

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

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

static const int MAXN = 1400;
static const int MAXM = 500000;
static const int MAXL = (MAXN-1) * 500;
static const int MAXLGL = 20;

static queue<bool> RQB;
static int needBits[MAXN+1];

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

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

static int N, M, K;

static void send(bool x) { SendB(x); }
static void sendVertex(int v) {
	//int l = needBits[K+1];
	int l = needBits[N];
	for(int i = 0; i < l; i++) send(v & (1<<l));
}
static void sendInt(int x) {
	int l = MAXLGL;
	for(int i = 0; i < l; i++) send(x & (1<<i));
}
static int getInt(int l) {
	int ret = 0;
	for(int i = 0; i < l; i++) {
		if(RQB.front()) ret |= 1 << i;
		RQB.pop();
	}
	return ret;
}
static int getVertex() { return getInt(needBits[N]); }
static int getInt() { return getInt(MAXLGL); }


static int getMinDist() {
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	return PQ.empty() ? MAXL : PQ.top().first;
}

static void sendInfo() {
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	if(PQ.empty()) {
		sendVertex(0);
		return;
	}
	int dst, idx;
	tie(dst, idx) = PQ.top();
	sendVertex(idx);
	sendInt(dst);
}

static void spread(int sidx, int sdst) {
	if(!chk[sidx]) {
		chk[sidx] = true;
		DP[sidx] = sdst;
		K++;
		PQ.push({sidx, sdst});
		for(int idx, dst; !PQ.empty();) {
			tie(dst, idx) = PQ.top();
			if(!chk[idx]) break;
			PQ.pop();
			if(DP[idx] < dst) continue;
			for(int e : G[idx]) {
				int v = A[e]^B[e]^idx;
				int ndst = dst + C[e];
				if(DP[v] <= ndst) continue;
				DP[v] = ndst;
				PQ.push({ndst, v});
			}
		}
	}
	sendInfo();
}
static void spreadTop() {
	if(K == N) return;
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	if(!PQ.empty()) spread(PQ.top().second, PQ.top().first);
	else sendInfo();
}


static void init() {
	for(int i = 0, s, e;; i++) {
		s = 1<<i; e = s<<1;
		if(MAXN < s) break;
		for(int j = s; j < e && j <= MAXN; j++)
			needBits[j] = i;
	}
	for(int i = 0; i < M; i++) {
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}

	fill(DP, DP+N, MAXL);
	spread(0, 0);
}

static bool stayForLen = false;
static int stayIndex;
void ReceiveB(bool x) {
	RQB.push(x);

	if(stayForLen) {
		int l = MAXLGL;
		if(sz(RQB) < l) return;
		int dst = getInt();
		if(getMinDist() < l) {
			spreadTop();
			return;
		}
		spread(l, dst);
		return;
	}

	int l = needBits[N];
	if(sz(RQB) == l) {
		int v = getVertex();
		if(!v) {
			spreadTop();
		} else {
			stayForLen = true;
			stayIndex = v;
		}
	}
}

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();
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1248 KB Output is correct
2 Runtime error 3 ms 836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Failed 125 ms 948 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Failed 125 ms 948 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Failed 125 ms 948 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -