oj.uz

Submission #112231

# Submission time Handle Problem Language Result Execution time Memory
112231 2019-05-17T22:28:35 Z model_code Two Transportations (JOI19_transportations) C++17
Evaluating test 3-7
 979 ms 27700 KB 
#include "Azer.h"
#include <queue>

using namespace std;

namespace {

const int INF = 1000000007;

int n;
vector<pair<int, int> > *E;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
int Lcnt;
int Mcnt;
int buf;
bool mode;
int dist_m;
int d_sent;

void updateQ(int N) {
	for(auto e: E[N]) {
		if(dist[N] + e.second < -dist[e.first]) {
			dist[e.first] = -(dist[N] + e.second);
			PQ.push(make_pair(dist[N] + e.second, e.first));
		}
	}
}

void getQ() {
	if(Lcnt == 0) return;
	Lcnt--;
	for(;;) {
		if(PQ.empty()) {
			d_sent = (1 << 9) - 1;
			for(int i = 8; i >= 0; i--) {
				SendA((d_sent >> i) & 1);
			}
			return;
		}
		pair<int, int> rem = PQ.top();
		if(rem.first + dist[rem.second] == 0) {
			d_sent = rem.first - dist_m;
			for(int i = 8; i >= 0; i--) {
				SendA((d_sent >> i) & 1);
			}
			return;
		}
		PQ.pop();
	}
}

} // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	n = N;
	E = new vector<pair<int, int> >[N];
	for(int i = 0; i < A; i++) {
		E[U[i]].push_back(make_pair(V[i], C[i]));
		E[V[i]].push_back(make_pair(U[i], C[i]));
	}
	dist.push_back(0);
	for(int i = 1; i < N; i++) {
		dist.push_back(-INF);
	}
	Lcnt = N - 1;
	dist_m = 0;
	updateQ(0);
	getQ();
	mode = false;
	Mcnt = 0;
	buf = 0;
}

void ReceiveA(bool x) {
	buf *= 2;
	buf += x;
	if(mode) {
		if(++Mcnt == 11) {
			dist_m += d_sent;
			dist[buf] = dist_m;
			updateQ(buf);
			getQ();
			mode = false;
			Mcnt = 0;
			buf = 0;
		}
	} else {
		if(++Mcnt == 9) {
			if(buf >= d_sent) {
				int N = PQ.top().second;
				for(int i = 10; i >= 0; i--) {
					SendA((N >> i) & 1);
				}
				dist_m += d_sent;
				dist[N] = dist_m;
				updateQ(N);
				getQ();
			} else {
				d_sent = buf;
				mode = true;
			}
			Mcnt = 0;
			buf = 0;
		}
	}
}

std::vector<int> Answer() {
	return dist;
}
#include "Baijan.h"
#include <queue>

using namespace std;

namespace {

const int INF = 1000000007;
int n;
vector<pair<int, int> > *E;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
int Lcnt;
int Mcnt;
int buf;
bool mode;
int dist_m;
int d_sent;

void updateQ(int N) {
	for(auto e: E[N]) {
		if(dist[N] + e.second < -dist[e.first]) {
			dist[e.first] = -(dist[N] + e.second);
			PQ.push(make_pair(dist[N] + e.second, e.first));
		}
	}
}

void getQ() {
	if(Lcnt == 0) return;
	Lcnt--;
	for(;;) {
		if(PQ.empty()) {
			d_sent = (1 << 9) - 1;
			for(int i = 8; i >= 0; i--) {
				SendB((d_sent >> i) & 1);
			}
			return;
		}
		pair<int, int> rem = PQ.top();
		if(rem.first + dist[rem.second] == 0) {
			d_sent = rem.first - dist_m;
			for(int i = 8; i >= 0; i--) {
				SendB((d_sent >> i) & 1);
			}
			return;
		}
		PQ.pop();
	}
}

} // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
	n = N;
	E = new vector<pair<int, int> >[N];
	for(int i = 0; i < B; i++) {
		E[S[i]].push_back(make_pair(T[i], D[i]));
		E[T[i]].push_back(make_pair(S[i], D[i]));
	}
	dist.push_back(0);
	for(int i = 1; i < N; i++) {
		dist.push_back(-INF);
	}
	Lcnt = N - 1;
	dist_m = 0;
	updateQ(0);
	getQ();
	mode = false;
	Mcnt = 0;
	buf = 0;
}

void ReceiveB(bool y) {
	buf *= 2;
	buf += y;
	if(mode) {
		if(++Mcnt == 11) {
			dist_m += d_sent;
			dist[buf] = dist_m;
			updateQ(buf);
			getQ();
			mode = false;
			Mcnt = 0;
			buf = 0;
		}
	} else {
		if(++Mcnt == 9) {
			if(buf > d_sent) {
				int N = PQ.top().second;
				for(int i = 10; i >= 0; i--) {
					SendB((N >> i) & 1);
				}
				dist_m += d_sent;
				dist[N] = dist_m;
				updateQ(N);
				getQ();
			} else {
				d_sent = buf;
				mode = true;
			}
			Mcnt = 0;
			buf = 0;
		}
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 920 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 536 ms 920 KB Output is correct
4 Correct 819 ms 10348 KB Output is correct
5 Correct 31 ms 856 KB Output is correct
6 Correct 642 ms 2332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 556 ms 1004 KB Output is correct
3 Correct 667 ms 1060 KB Output is correct
4 Correct 808 ms 27700 KB Output is correct
5 Correct 903 ms 24328 KB Output is correct
6 Correct 140 ms 748 KB Output is correct
7 Correct 979 ms 24484 KB Output is correct