oj.uz

Submission #673704

# Submission time Handle Problem Language Result Execution time Memory
673704 2022-12-21T18:49:11 Z rainboy Two Transportations (JOI19_transportations) C++17
6 / 100
 751 ms 43656 KB 
#include "Azer.h"
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace A {
	int min(int a, int b) { return a < b ? a : b; }
	const int N = 2000, INF = 0x3f3f3f3f;
	int ww[N][N], dd[N], n, n1, d_, s, k, z; char used[N];
	void relax(int i, long long d) {
		dd[i] = d, used[i] = 1;
		for (int j = 0; j < n; j++)
			if (!used[j])
				dd[j] = min(dd[j], dd[i] + ww[i][j]);
	}
	int nxt() {
		int i_ = -1;
		for (int i = 0; i < n; i++)
			if (!used[i] && dd[i] != INF && (i_ == -1 || dd[i_] > dd[i]))
				i_ = i;
		return i_;
	}
}

void InitA(int n_, int m, vi ii, vi jj, vi ww_) {
	A::n = n_, A::n1 = 0;
	for (int i = 0; i < A::n; i++)
		memset(A::ww[i], 0x3f, A::n * sizeof *A::ww[i]);
	for (int h = 0; h < m; h++) {
		int i = ii[h], j = jj[h], w = ww_[h];
		A::ww[i][j] = A::ww[j][i] = w;
	}
	memset(A::dd, 0x3f, A::n * sizeof *A::dd), A::dd[0] = A::d_ = 0;
	A::s = 0, A::k = 0, A::z = 0;
	for (int l = 0; l < 9; l++)
		SendA((A::dd[0] - A::d_) >> l & 1);
	for (int l = 0; l < 11; l++)
		SendA(0 >> l & 1);
	A::relax(0, 0);
}

void ReceiveA(bool x) {
	if (x)
		A::z |= 1 << A::k;
	A::k++;
	if (A::k != (A::s == 0 ? 9 : 20))
		return;
	if (A::s == 1 && A::k == 20) {
		int i = A::z >> 9;
		A::relax(i, A::d_);
		A::z &= (1 << 9) - 1;
	}
	if (++A::n1 == A::n)
		return;
	int i = A::nxt(), d = i == -1 ? (1 << 9) - 1 : min(A::dd[i] - A::d_, (1 << 9) - 1);
	for (int l = 0; l < 9; l++)
		SendA(d >> l & 1);
	if (d <= A::z) {
		A::s = 0;
		for (int l = 0; l < 11; l++)
			SendA(i >> l & 1);
		A::relax(i, A::d_ += d);
	} else {
		A::s = 1;
		A::d_ += A::z;
	}
	A::k = 0, A::z = 0;
}

vi Answer() {
	return vi(A::dd, A::dd + A::n);
}
#include "Baijan.h"
#include <cstring>
#include <vector>

using namespace std;

typedef vector<int> vi;

namespace B {
	int min(int a, int b) { return a < b ? a : b; }
	const int N = 2000, INF = 0x3f3f3f3f;
	int ww[N][N], dd[N], n, n1, d_, k, z; char used[N];
	void relax(int i, long long d) {
		dd[i] = d, used[i] = 1;
		for (int j = 0; j < n; j++)
			if (!used[j])
				dd[j] = min(dd[j], dd[i] + ww[i][j]);
	}
	int nxt() {
		int i_ = -1;
		for (int i = 0; i < n; i++)
			if (!used[i] && dd[i] != INF && (i_ == -1 || dd[i_] > dd[i]))
				i_ = i;
		return i_;
	}
}

void InitB(int n_, int m, vi ii, vi jj, vi ww_) {
	B::n = n_;
	for (int i = 0; i < B::n; i++)
		memset(B::ww[i], 0x3f, B::n * sizeof *B::ww[i]);
	for (int h = 0; h < m; h++) {
		int i = ii[h], j = jj[h], w = ww_[h];
		B::ww[i][j] = B::ww[j][i] = w;
	}
	memset(B::dd, 0x3f, B::n * sizeof *B::dd), B::dd[0] = B::d_ = 0;
	B::k = 0, B::z = 0;
}

void ReceiveB(bool y) {
	if (y)
		B::z |= 1 << B::k;
	B::k++;
	if (B::k == 9) {
		int i = B::nxt();
		if (i != -1 && B::d_ + B::z > B::dd[i]) {
			B::relax(i, B::d_ = B::dd[i]);
			int j = B::nxt(), d = j == -1 ? (1 << 9) - 1 : min(B::dd[j] - B::d_, (1 << 9) - 1);
			for (int l = 0; l < 9; l++)
				SendB(d >> l & 1);
			for (int l = 0; l < 11; l++)
				SendB(i >> l & 1);
			B::k = 0, B::z = 0;
		}
	} else if (B::k == 20) {
		int i = B::z >> 9, j, d = B::z & (1 << 9) - 1;
		B::relax(i, B::d_ = d);
		j = B::nxt(), d = j == -1 ? (1 << 9) - 1 : min(B::dd[j] - B::d_, (1 << 9) - 1);
		for (int l = 0; l < 9; l++)
			SendB(d >> l & 1);
		B::k = 0, B::z = 0;
	}
}

Compilation message

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:56:45: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   56 |   int i = B::z >> 9, j, d = B::z & (1 << 9) - 1;
      |                                    ~~~~~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 31888 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 588 ms 31876 KB Output is correct
4 Correct 606 ms 36908 KB Output is correct
5 Correct 31 ms 1424 KB Output is correct
6 Correct 556 ms 32468 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 546 ms 31900 KB Output is correct
3 Correct 484 ms 31896 KB Output is correct
4 Correct 751 ms 43656 KB Output is correct
5 Correct 494 ms 43548 KB Output is correct
6 Correct 121 ms 5008 KB Output is correct
7 Incorrect 604 ms 43588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 7056 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 7 ms 7056 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 7 ms 7056 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 594 ms 31888 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 588 ms 31876 KB Output is correct
4 Correct 606 ms 36908 KB Output is correct
5 Correct 31 ms 1424 KB Output is correct
6 Correct 556 ms 32468 KB Output is correct
7 Correct 2 ms 400 KB Output is correct
8 Correct 546 ms 31900 KB Output is correct
9 Correct 484 ms 31896 KB Output is correct
10 Correct 751 ms 43656 KB Output is correct
11 Correct 494 ms 43548 KB Output is correct
12 Correct 121 ms 5008 KB Output is correct
13 Incorrect 604 ms 43588 KB Output isn't correct
14 Halted 0 ms 0 KB -