oj.uz

Submission #469615

# Submission time Handle Problem Language Result Execution time Memory
469615 2021-09-01T12:47:12 Z jhwest2 Two Transportations (JOI19_transportations) C++17
6 / 100
 752 ms 10212 KB 
#include "Azer.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;

namespace {

	const int M = 2e3 + 10, INF = 2e9 + 10;
	int n, Dist[M];

	priority_queue<pint, vector<pint>, greater<pint>> Q;
	vector<pint> G[M];

	int cnt = 0, last = 0, bits = 0, type = 0, rnd = 0;
}

void InitA(int N, int a, vector<int> U, vector<int> V, vector<int> C) {
	n = N;
	for (int i = 0; i < n; i++) Dist[i] = INF;
	for (int i = 0; i < a; i++) {
		G[U[i]].emplace_back(C[i], V[i]);
		G[V[i]].emplace_back(C[i], U[i]);
	}
	Dist[0] = 0;
	for (auto [a, b] : G[0]) {
		Q.emplace(a, b);
	}
	if (Q.empty()) {
		for (int i = 0; i < 9; i++) SendA(1);
	}
	else {
		auto [a, b] = Q.top();
		for (int i = 0; i < 9; i++) {
			SendA(a >> i & 1);
		}
	}
	rnd = n - 1;
}

void ReceiveA(bool x) {
	if (type == 0) {
		if (cnt != 8) {
			bits |= x << cnt;
			cnt += 1;
			return;
		}
		bits |= x << cnt;

		
		if (Q.empty() || Q.top().va > last + bits) {
			cnt = 0;
			type = 2;
			last = last + bits;
			bits = 0;
			return;
		}
		
		auto [a, b] = Q.top(); Q.pop();
		
		Dist[b] = a;
		last = Dist[b];
		type = cnt = bits = 0;
		
		
		for (auto [c, d] : G[b]) {
			if (Dist[d] == INF) Q.emplace(last + c, d);
		}
		while (!Q.empty() && Dist[Q.top().vb] != INF) {
			Q.pop();
		}

		int kth = 0;
		for (int i = 0; i < b; i++) {
			if (Dist[i] == INF) kth += 1;
		}
		for (int i = 0; rnd >> i; i++) {
			SendA(kth >> i & 1);			
		}

		rnd -= 1;
		if (rnd == 0) return;

		int d = (Q.empty() ? 511 : Q.top().va - last);
		for (int i = 0; i < 9; i++) {
			SendA(d >> i & 1);
		}
		return;
	}
	if (rnd >> (cnt + 1)) {
		bits |= x << cnt;
		cnt += 1;
		return;
	}
	bits |= x << cnt;

	int kth = 0, b = 0;
	for (int i = 0; i < M; i++) if (Dist[i] == INF) {
		if (kth == bits) {
			b = i; break;
		}
		kth += 1;
	}

	Dist[b] = last;
	type = cnt = bits = 0;
	
	for (auto [c, d] : G[b]) {
		if (Dist[d] == INF) Q.emplace(last + c, d);
	}
	while (!Q.empty() && Dist[Q.top().vb] != INF) {
		Q.pop();
	}

	rnd -= 1;
	if (rnd == 0) return;

	int d = (Q.empty() ? 511 : Q.top().va - last);
	for (int i = 0; i < 9; i++) {
		SendA(d >> i & 1);
	}
}

vector<int> Answer() {
	vector<int> ret;
	for (int i = 0; i < n; i++) {
		ret.push_back(Dist[i]);
	}
	return ret;
}

#include "Baijan.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;

namespace {

	const int M = 2e3 + 10, INF = 2e9 + 10;
	int n, Dist[M];

	priority_queue<pint, vector<pint>, greater<pint>> Q;
	vector<pint> G[M];

	int cnt = 0, last = 0, bits = 0, type = 0, rnd = 0;
}

void InitB(int N, int b, vector<int> U, vector<int> V, vector<int> C) {
	n = N;
	for (int i = 0; i < n; i++) Dist[i] = INF;
	for (int i = 0; i < b; i++) {
		G[U[i]].emplace_back(C[i], V[i]);
		G[V[i]].emplace_back(C[i], U[i]);
	}
	Dist[0] = 0;
	for (auto [a, b] : G[0]) {
		Q.emplace(a, b);
	}
	if (Q.empty()) {
		for (int i = 0; i < 9; i++) SendB(1);
	}
	else {
		auto [a, b] = Q.top();
		for (int i = 0; i < 9; i++) {
			SendB(a >> i & 1);
		}
	}
	rnd = n - 1;
}

void ReceiveB(bool x) {
	if (type == 0) {
		if (cnt != 8) {
			bits |= x << cnt;
			cnt += 1;
			return;
		}
		bits |= x << cnt;

		
		if (Q.empty() || Q.top().va > last + bits) {
			cnt = 0;
			type = 2;
			last = last + bits;
			bits = 0;
			return;
		}
		
		auto [a, b] = Q.top(); Q.pop();
		
		Dist[b] = a;
		last = Dist[b];
		type = cnt = bits = 0;
		
		
		for (auto [c, d] : G[b]) {
			if (Dist[d] == INF) Q.emplace(last + c, d);
		}
		while (!Q.empty() && Dist[Q.top().vb] != INF) {
			Q.pop();
		}

		int kth = 0;
		for (int i = 0; i < b; i++) {
			if (Dist[i] == INF) kth += 1;
		}
		for (int i = 0; rnd >> i; i++) {
			SendB(kth >> i & 1);			
		}

		rnd -= 1;
		if (rnd == 0) return;
		
		int d = (Q.empty() ? 511 : Q.top().va - last);
		for (int i = 0; i < 9; i++) {
			SendB(d >> i & 1);
		}
		return;
	}
	if (rnd >> (cnt + 1)) {
		bits |= x << cnt;
		cnt += 1;
		return;
	}
	bits |= x << cnt;

	int kth = 0, b = 0;
	for (int i = 0; i < M; i++) if (Dist[i] == INF) {
		if (kth == bits) {
			b = i; break;
		}
		kth += 1;
	}

	Dist[b] = last;
	type = cnt = bits = 0;
	
	for (auto [c, d] : G[b]) {
		if (Dist[d] == INF) Q.emplace(last + c, d);
	}
	while (!Q.empty() && Dist[Q.top().vb] != INF) {
		Q.pop();
	}

	rnd -= 1;
	if (rnd == 0) return;

	int d = (Q.empty() ? 511 : Q.top().va - last);
	for (int i = 0; i < 9; i++) {
		SendB(d >> i & 1);
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 768 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 609 ms 776 KB Output is correct
4 Correct 752 ms 10212 KB Output is correct
5 Correct 31 ms 896 KB Output is correct
6 Correct 630 ms 2588 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 648 KB Output is correct
2 Correct 578 ms 728 KB Output is correct
3 Runtime error 249 ms 468 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 320 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 320 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 320 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 768 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 609 ms 776 KB Output is correct
4 Correct 752 ms 10212 KB Output is correct
5 Correct 31 ms 896 KB Output is correct
6 Correct 630 ms 2588 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 578 ms 728 KB Output is correct
9 Runtime error 249 ms 468 KB Execution killed with signal 13
10 Halted 0 ms 0 KB -