oj.uz

Submission #123361

# Submission time Handle Problem Language Result Execution time Memory
123361 2019-07-01T08:25:04 Z 윤교준(#3020) Two Transportations (JOI19_transportations) C++14
0 / 100
 401 ms 1248 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 bool debug = 0;

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 set<pii> BPQ;

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

static int N, M, K;

static void spread(int, int, bool);

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<<i));
}
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(debug) {
		printf("START SENDINFO A\n");
		for(int i = 0; i < N; i++) printf("%d ", int(chk[i]));
		puts("");
	}
	if(K == N) return;
	for(int dst, idx; !PQ.empty(); PQ.pop()) {
		tie(dst, idx) = PQ.top();
		if(chk[idx]) continue;
		if(BPQ.end() == BPQ.find({idx, dst})) break;
		spread(idx, dst, true);
	}
	if(PQ.empty()) {
		if(debug) printf("SENDINFO A 0\n");
		sendVertex(0);
		return;
	}
	int dst, idx;
	tie(dst, idx) = PQ.top();
	sendVertex(idx);
	sendInt(dst);
	if(debug) printf("SENDINFO A %d %d\n", idx, dst);
}

static void spread(int sidx, int sdst, bool ign = false) {
	if(K == N) return;
	if(debug) printf("SPREAD A : %d %d\n", sidx, sdst);
	if(!chk[sidx]) {
		chk[sidx] = true;
		DP[sidx] = sdst;
		K++;
		PQ.push({sdst, sidx});
		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});
			}
		}
	}
	if(debug) {
		printf("FIN A %d / %d\n", N, K);
		for(int i = 0; i < N; i++) printf("%d ", DP[i]);
		puts("");
		for(int i = 0; i < N; i++) printf("%d ", int(chk[i]));
		puts("");

		auto V = PQ;
		puts("PQ");
		for(int a, b; !V.empty(); V.pop()) {
			tie(a, b) = V.top();
			printf("%d %d\n", a, b);
		}
		puts("PQ END");
	}
	if(!ign) sendInfo();
}
static void spreadTop() {
	if(debug) {
		puts("SPREADTOP A");
		auto V = PQ;
		puts("PQ");
		for(int a, b; !V.empty(); V.pop()) {
			tie(a, b) = V.top();
			printf("%d %d\n", a, b);
		}
		puts("PQ END");
	}
	if(K == N) return;
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	spread(PQ.top().second, PQ.top().first);
}

static void consider(int sidx, int sdst) {
	if(DP[sidx] <= sdst) return;
	if(debug) printf("CONSIDER A %d %d\n", sidx, sdst);
	priority_queue<pii, vector<pii>, greater<pii>> V;
	DP[sidx] = sdst;
	V.push({sdst, sidx});
	PQ.push({sdst, sidx});
	for(int idx, dst; !V.empty();) {
		tie(dst, idx) = V.top(); V.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;
			V.push({ndst, v});
			PQ.push({ndst, v});
			DP[v] = ndst;
		}
	}
}


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;
		stayForLen = false;
		int dst = getInt();
		BPQ.insert({stayIndex, dst});
		if(debug) printf("GETINFO A %d %d\n", stayIndex, dst);
		if(getMinDist() < dst) {
			consider(stayIndex, dst);
			spreadTop();
			return;
		}
		spread(stayIndex, dst);
		return;
	}

	int l = needBits[N];
	if(sz(RQB) == l) {
		int v = getVertex();
		if(debug) printf("GETINFO A %d\n", v);
		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 bool debug = 0;

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 set<pii> APQ;
static bitset<MAXN> chk;


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

static int N, M, K;

static void spread(int, int, bool);

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<<i));
}
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(debug) puts("SENDINFO B START");
	for(int idx, dst; !PQ.empty(); PQ.pop()) {
		tie(dst, idx) = PQ.top();
		if(chk[idx]) continue;
		if(APQ.end() == APQ.find({idx, dst})) break;
		spread(idx, dst, true);
	}
	if(PQ.empty()) {
		if(debug) printf("SENDINFO B 0\n");
		sendVertex(0);
		return;
	}
	int dst, idx;
	tie(dst, idx) = PQ.top();
	sendVertex(idx);
	sendInt(dst);
	if(debug) printf("SENDINFO B %d %d\n", idx, dst);
}

static void spread(int sidx, int sdst, bool ign = false) {
	if(debug) printf("SPREAD B %d %d\n", sidx, sdst);
	if(!chk[sidx]) {
		chk[sidx] = true;
		DP[sidx] = sdst;
		K++;
		PQ.push({sdst, sidx});
		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});
			}
		}
	}
	if(debug) {
		puts("FIN B");
		for(int i = 0; i < N; i++) printf("%d ", DP[i]);
		for(int i = 0; i < N; i++) printf("%d ", int(chk[i]));
		puts("");
	}
	if(!ign) sendInfo();
	if(debug) puts("SPREAD B END");
}
static void spreadTop() {
	for(; !PQ.empty() && chk[PQ.top().second]; PQ.pop());
	if(!PQ.empty()) spread(PQ.top().second, PQ.top().first);
	else sendInfo();
}

static void consider(int sidx, int sdst) {
	if(DP[sidx] <= sdst) return;
	priority_queue<pii, vector<pii>, greater<pii>> V;
	DP[sidx] = sdst;
	V.push({sdst, sidx});
	PQ.push({sdst, sidx});
	for(int idx, dst; !V.empty();) {
		tie(dst, idx) = V.top(); V.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;
			V.push({ndst, v});
			PQ.push({ndst, v});
			DP[v] = ndst;
		}
	}
}


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, true);
}

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

	if(stayForLen) {
		int l = MAXLGL;
		if(sz(RQB) < l) return;
		stayForLen = false;
		int dst = getInt();
		APQ.insert({stayIndex, dst});
		if(debug) printf("GETINFO B %d %d / %d\n", stayIndex, dst, getMinDist());
		if(getMinDist() < dst) {
			consider(stayIndex, dst);
			spreadTop();
			return;
		}
		spread(stayIndex, dst);
		return;
	}

	int l = needBits[N];
	if(sz(RQB) == l) {
		int v = getVertex();
		if(debug) printf("GETINFO B %d\n", v);
		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 3 ms 880 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 8 ms 1248 KB Output is correct
2 Runtime error 3 ms 840 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 4 ms 1064 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 Incorrect 401 ms 656 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 656 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 656 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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