oj.uz

답안 #673706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673706 2022-12-21T18:57:50 Z rainboy Two Transportations (JOI19_transportations) C++17
100 / 100
 859 ms 55316 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

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 31888 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 487 ms 31872 KB Output is correct
4 Correct 556 ms 36996 KB Output is correct
5 Correct 35 ms 1552 KB Output is correct
6 Correct 565 ms 32512 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 400 KB Output is correct
2 Correct 594 ms 31884 KB Output is correct
3 Correct 615 ms 31936 KB Output is correct
4 Correct 692 ms 43532 KB Output is correct
5 Correct 598 ms 43544 KB Output is correct
6 Correct 105 ms 5008 KB Output is correct
7 Correct 712 ms 43528 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 536 ms 31896 KB Output is correct
2 Correct 1 ms 400 KB Output is correct
3 Correct 529 ms 31888 KB Output is correct
4 Correct 458 ms 31896 KB Output is correct
5 Correct 513 ms 31840 KB Output is correct
6 Correct 613 ms 31904 KB Output is correct
7 Correct 482 ms 31908 KB Output is correct
8 Correct 559 ms 31928 KB Output is correct
9 Correct 489 ms 31888 KB Output is correct
10 Correct 538 ms 31876 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 13968 KB Output is correct
2 Correct 214 ms 14028 KB Output is correct
3 Correct 263 ms 19472 KB Output is correct
4 Correct 254 ms 13968 KB Output is correct
5 Correct 278 ms 18940 KB Output is correct
6 Correct 183 ms 14040 KB Output is correct
7 Correct 213 ms 13968 KB Output is correct
8 Correct 201 ms 13968 KB Output is correct
9 Correct 356 ms 23476 KB Output is correct
10 Correct 301 ms 23596 KB Output is correct
11 Correct 445 ms 33004 KB Output is correct
12 Correct 279 ms 28140 KB Output is correct
13 Correct 246 ms 13944 KB Output is correct
14 Correct 1 ms 400 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 13968 KB Output is correct
2 Correct 214 ms 14028 KB Output is correct
3 Correct 263 ms 19472 KB Output is correct
4 Correct 254 ms 13968 KB Output is correct
5 Correct 278 ms 18940 KB Output is correct
6 Correct 183 ms 14040 KB Output is correct
7 Correct 213 ms 13968 KB Output is correct
8 Correct 201 ms 13968 KB Output is correct
9 Correct 356 ms 23476 KB Output is correct
10 Correct 301 ms 23596 KB Output is correct
11 Correct 445 ms 33004 KB Output is correct
12 Correct 279 ms 28140 KB Output is correct
13 Correct 246 ms 13944 KB Output is correct
14 Correct 1 ms 400 KB Output is correct
15 Correct 274 ms 17720 KB Output is correct
16 Correct 251 ms 17680 KB Output is correct
17 Correct 165 ms 17816 KB Output is correct
18 Correct 332 ms 22312 KB Output is correct
19 Correct 207 ms 17812 KB Output is correct
20 Correct 300 ms 22544 KB Output is correct
21 Correct 255 ms 17808 KB Output is correct
22 Correct 262 ms 17808 KB Output is correct
23 Correct 371 ms 29468 KB Output is correct
24 Correct 390 ms 29648 KB Output is correct
25 Correct 478 ms 41240 KB Output is correct
26 Correct 433 ms 34156 KB Output is correct
27 Correct 288 ms 17776 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 13968 KB Output is correct
2 Correct 214 ms 14028 KB Output is correct
3 Correct 263 ms 19472 KB Output is correct
4 Correct 254 ms 13968 KB Output is correct
5 Correct 278 ms 18940 KB Output is correct
6 Correct 183 ms 14040 KB Output is correct
7 Correct 213 ms 13968 KB Output is correct
8 Correct 201 ms 13968 KB Output is correct
9 Correct 356 ms 23476 KB Output is correct
10 Correct 301 ms 23596 KB Output is correct
11 Correct 445 ms 33004 KB Output is correct
12 Correct 279 ms 28140 KB Output is correct
13 Correct 246 ms 13944 KB Output is correct
14 Correct 1 ms 400 KB Output is correct
15 Correct 274 ms 17720 KB Output is correct
16 Correct 251 ms 17680 KB Output is correct
17 Correct 165 ms 17816 KB Output is correct
18 Correct 332 ms 22312 KB Output is correct
19 Correct 207 ms 17812 KB Output is correct
20 Correct 300 ms 22544 KB Output is correct
21 Correct 255 ms 17808 KB Output is correct
22 Correct 262 ms 17808 KB Output is correct
23 Correct 371 ms 29468 KB Output is correct
24 Correct 390 ms 29648 KB Output is correct
25 Correct 478 ms 41240 KB Output is correct
26 Correct 433 ms 34156 KB Output is correct
27 Correct 288 ms 17776 KB Output is correct
28 Correct 380 ms 22432 KB Output is correct
29 Correct 386 ms 22472 KB Output is correct
30 Correct 344 ms 34084 KB Output is correct
31 Correct 382 ms 22452 KB Output is correct
32 Correct 434 ms 31548 KB Output is correct
33 Correct 325 ms 22472 KB Output is correct
34 Correct 380 ms 22536 KB Output is correct
35 Correct 374 ms 22536 KB Output is correct
36 Correct 479 ms 34080 KB Output is correct
37 Correct 469 ms 34188 KB Output is correct
38 Correct 603 ms 45908 KB Output is correct
39 Correct 642 ms 41208 KB Output is correct
40 Correct 329 ms 22416 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 558 ms 31888 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 487 ms 31872 KB Output is correct
4 Correct 556 ms 36996 KB Output is correct
5 Correct 35 ms 1552 KB Output is correct
6 Correct 565 ms 32512 KB Output is correct
7 Correct 1 ms 400 KB Output is correct
8 Correct 594 ms 31884 KB Output is correct
9 Correct 615 ms 31936 KB Output is correct
10 Correct 692 ms 43532 KB Output is correct
11 Correct 598 ms 43544 KB Output is correct
12 Correct 105 ms 5008 KB Output is correct
13 Correct 712 ms 43528 KB Output is correct
14 Correct 536 ms 31896 KB Output is correct
15 Correct 1 ms 400 KB Output is correct
16 Correct 529 ms 31888 KB Output is correct
17 Correct 458 ms 31896 KB Output is correct
18 Correct 513 ms 31840 KB Output is correct
19 Correct 613 ms 31904 KB Output is correct
20 Correct 482 ms 31908 KB Output is correct
21 Correct 559 ms 31928 KB Output is correct
22 Correct 489 ms 31888 KB Output is correct
23 Correct 538 ms 31876 KB Output is correct
24 Correct 229 ms 13968 KB Output is correct
25 Correct 214 ms 14028 KB Output is correct
26 Correct 263 ms 19472 KB Output is correct
27 Correct 254 ms 13968 KB Output is correct
28 Correct 278 ms 18940 KB Output is correct
29 Correct 183 ms 14040 KB Output is correct
30 Correct 213 ms 13968 KB Output is correct
31 Correct 201 ms 13968 KB Output is correct
32 Correct 356 ms 23476 KB Output is correct
33 Correct 301 ms 23596 KB Output is correct
34 Correct 445 ms 33004 KB Output is correct
35 Correct 279 ms 28140 KB Output is correct
36 Correct 246 ms 13944 KB Output is correct
37 Correct 1 ms 400 KB Output is correct
38 Correct 274 ms 17720 KB Output is correct
39 Correct 251 ms 17680 KB Output is correct
40 Correct 165 ms 17816 KB Output is correct
41 Correct 332 ms 22312 KB Output is correct
42 Correct 207 ms 17812 KB Output is correct
43 Correct 300 ms 22544 KB Output is correct
44 Correct 255 ms 17808 KB Output is correct
45 Correct 262 ms 17808 KB Output is correct
46 Correct 371 ms 29468 KB Output is correct
47 Correct 390 ms 29648 KB Output is correct
48 Correct 478 ms 41240 KB Output is correct
49 Correct 433 ms 34156 KB Output is correct
50 Correct 288 ms 17776 KB Output is correct
51 Correct 380 ms 22432 KB Output is correct
52 Correct 386 ms 22472 KB Output is correct
53 Correct 344 ms 34084 KB Output is correct
54 Correct 382 ms 22452 KB Output is correct
55 Correct 434 ms 31548 KB Output is correct
56 Correct 325 ms 22472 KB Output is correct
57 Correct 380 ms 22536 KB Output is correct
58 Correct 374 ms 22536 KB Output is correct
59 Correct 479 ms 34080 KB Output is correct
60 Correct 469 ms 34188 KB Output is correct
61 Correct 603 ms 45908 KB Output is correct
62 Correct 642 ms 41208 KB Output is correct
63 Correct 329 ms 22416 KB Output is correct
64 Correct 520 ms 31948 KB Output is correct
65 Correct 627 ms 43580 KB Output is correct
66 Correct 621 ms 43156 KB Output is correct
67 Correct 518 ms 31876 KB Output is correct
68 Correct 560 ms 31880 KB Output is correct
69 Correct 859 ms 55316 KB Output is correct
70 Correct 760 ms 52856 KB Output is correct
71 Correct 631 ms 33912 KB Output is correct
72 Correct 496 ms 32056 KB Output is correct