oj.uz

Submission #673705

# Submission time Handle Problem Language Result Execution time Memory
673705 2022-12-21T18:53:51 Z rainboy Two Transportations (JOI19_transportations) C++17
6 / 100
 629 ms 43572 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, int 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, int 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 600 ms 31880 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 556 ms 31880 KB Output is correct
4 Correct 536 ms 36816 KB Output is correct
5 Correct 24 ms 1424 KB Output is correct
6 Correct 545 ms 32464 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 400 KB Output is correct
2 Correct 483 ms 31928 KB Output is correct
3 Correct 548 ms 31952 KB Output is correct
4 Correct 629 ms 43548 KB Output is correct
5 Correct 623 ms 43572 KB Output is correct
6 Correct 108 ms 5008 KB Output is correct
7 Incorrect 498 ms 43540 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 10 ms 15944 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 6 ms 7060 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 6 ms 7060 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 6 ms 7060 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 600 ms 31880 KB Output is correct
2 Correct 0 ms 400 KB Output is correct
3 Correct 556 ms 31880 KB Output is correct
4 Correct 536 ms 36816 KB Output is correct
5 Correct 24 ms 1424 KB Output is correct
6 Correct 545 ms 32464 KB Output is correct
7 Correct 1 ms 400 KB Output is correct
8 Correct 483 ms 31928 KB Output is correct
9 Correct 548 ms 31952 KB Output is correct
10 Correct 629 ms 43548 KB Output is correct
11 Correct 623 ms 43572 KB Output is correct
12 Correct 108 ms 5008 KB Output is correct
13 Incorrect 498 ms 43540 KB Output isn't correct
14 Halted 0 ms 0 KB -