oj.uz

답안 #266610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
266610 2020-08-15T11:30:23 Z dolphingarlic Two Transportations (JOI19_transportations) C++14
100 / 100
 2450 ms 113344 KB 
#include "Azer.h"

#include <bits/stdc++.h>
using namespace std;

namespace {
int N, stage = 0, cnt, b_shortest, mx_so_far;
vector<pair<int, int>> graph[2000];
vector<int> shortest;
priority_queue<pair<int, int>> pq;
bool visited[2000];
pair<int, int> cand = {0, 0};

void reset() {
	visited[cand.second] = true;
	shortest[cand.second] = cand.first;
	mx_so_far = cand.first;
	for (pair<int, int> i : graph[cand.second])
		pq.push({-cand.first - i.second, i.first});
	N--;

	if (!N) return;

	while (pq.size() && visited[pq.top().second]) pq.pop();
	if (pq.size()) cand = {-pq.top().first, pq.top().second};
	else cand = {mx_so_far + 511, -1};

	for (int i = 0; i < 9; i++) SendA(((cand.first - mx_so_far) & (1 << i)) >> i);
	cnt = stage = b_shortest = 0;
}
}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
	::N = N;
	shortest.resize(N);
	for (int i = 0; i < A; i++) {
		graph[U[i]].push_back({V[i], C[i]});
		graph[V[i]].push_back({U[i], C[i]});
	}
	reset();
}

void ReceiveA(bool x) {
	if (stage == 0) {
		b_shortest |= x << cnt++;
		if (cnt == 9) {
			if (b_shortest == 511) {
				for (int i = 0; i < 11; i++) SendA((cand.second & (1 << i)) >> i);
				reset();
			} else {
				stage++;
				cand = {mx_so_far + b_shortest, 0};
				cnt = 0;
			}
		}
	} else {
		cand.second |= x << cnt++;
		if (cnt == 11) reset();
	}
}

vector<int> Answer() {
	return shortest;
}

#include "Baijan.h"

#include <bits/stdc++.h>
using namespace std;

namespace {
int N, stage = 0, cnt, a_shortest, mx_so_far;
vector<pair<int, int>> graph[2000];
vector<int> shortest;
priority_queue<pair<int, int>> pq;
bool visited[2000];
pair<int, int> cand = {0, 0};

void reset() {
	visited[cand.second] = true;
	shortest[cand.second] = cand.first;
	mx_so_far = cand.first;
	for (pair<int, int> i : graph[cand.second])
		pq.push({-cand.first - i.second, i.first});

	while (pq.size() && visited[pq.top().second]) pq.pop();
	if (pq.size()) cand = {-pq.top().first, pq.top().second};
	else cand = {mx_so_far + 511, -1};

	cnt = stage = a_shortest = 0;
}
}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
	::N = N;
	shortest.resize(N);
	for (int i = 0; i < B; i++) {
		graph[S[i]].push_back({T[i], D[i]});
		graph[T[i]].push_back({S[i], D[i]});
	}
	reset();
}

void ReceiveB(bool y) {
	if (stage == 0) {
		a_shortest |= y << cnt++;
		if (cnt == 9) {
			if (a_shortest > cand.first - mx_so_far) {
				for (int i = 0; i < 9; i++) SendB(((cand.first - mx_so_far) & (1 << i)) >> i);
				for (int i = 0; i < 11; i++) SendB((cand.second & (1 << i)) >> i);
				reset();
			} else {
				for (int i = 0; i < 9; i++) SendB(1);
				cnt = 0;
				cand = {a_shortest + mx_so_far, 0};
				stage++;
			}
		}
	} else if (stage == 1) {
		cand.second |= y << cnt++;
		if (cnt == 11) reset();
	}
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 928 ms 1768 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 826 ms 1536 KB Output is correct
4 Correct 1225 ms 20192 KB Output is correct
5 Correct 66 ms 2016 KB Output is correct
6 Correct 1028 ms 5600 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 979 ms 1792 KB Output is correct
3 Correct 1056 ms 1792 KB Output is correct
4 Correct 2013 ms 54880 KB Output is correct
5 Correct 1720 ms 57248 KB Output is correct
6 Correct 206 ms 1536 KB Output is correct
7 Correct 1455 ms 57840 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 876 ms 1632 KB Output is correct
2 Correct 4 ms 1280 KB Output is correct
3 Correct 862 ms 1536 KB Output is correct
4 Correct 1011 ms 1536 KB Output is correct
5 Correct 870 ms 1536 KB Output is correct
6 Correct 976 ms 1616 KB Output is correct
7 Correct 974 ms 1536 KB Output is correct
8 Correct 886 ms 1680 KB Output is correct
9 Correct 944 ms 1536 KB Output is correct
10 Correct 974 ms 2016 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 1768 KB Output is correct
2 Correct 486 ms 1648 KB Output is correct
3 Correct 781 ms 24416 KB Output is correct
4 Correct 414 ms 1760 KB Output is correct
5 Correct 766 ms 17424 KB Output is correct
6 Correct 504 ms 1536 KB Output is correct
7 Correct 386 ms 1760 KB Output is correct
8 Correct 456 ms 1536 KB Output is correct
9 Correct 847 ms 47024 KB Output is correct
10 Correct 1188 ms 47272 KB Output is correct
11 Correct 1530 ms 85392 KB Output is correct
12 Correct 1238 ms 79848 KB Output is correct
13 Correct 444 ms 1752 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 1768 KB Output is correct
2 Correct 486 ms 1648 KB Output is correct
3 Correct 781 ms 24416 KB Output is correct
4 Correct 414 ms 1760 KB Output is correct
5 Correct 766 ms 17424 KB Output is correct
6 Correct 504 ms 1536 KB Output is correct
7 Correct 386 ms 1760 KB Output is correct
8 Correct 456 ms 1536 KB Output is correct
9 Correct 847 ms 47024 KB Output is correct
10 Correct 1188 ms 47272 KB Output is correct
11 Correct 1530 ms 85392 KB Output is correct
12 Correct 1238 ms 79848 KB Output is correct
13 Correct 444 ms 1752 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 554 ms 1536 KB Output is correct
16 Correct 488 ms 1536 KB Output is correct
17 Correct 530 ms 1536 KB Output is correct
18 Correct 942 ms 17600 KB Output is correct
19 Correct 559 ms 1608 KB Output is correct
20 Correct 974 ms 18000 KB Output is correct
21 Correct 732 ms 1744 KB Output is correct
22 Correct 848 ms 1536 KB Output is correct
23 Correct 1038 ms 52840 KB Output is correct
24 Correct 1487 ms 52688 KB Output is correct
25 Correct 1918 ms 102632 KB Output is correct
26 Correct 1483 ms 89616 KB Output is correct
27 Correct 612 ms 2024 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 1768 KB Output is correct
2 Correct 486 ms 1648 KB Output is correct
3 Correct 781 ms 24416 KB Output is correct
4 Correct 414 ms 1760 KB Output is correct
5 Correct 766 ms 17424 KB Output is correct
6 Correct 504 ms 1536 KB Output is correct
7 Correct 386 ms 1760 KB Output is correct
8 Correct 456 ms 1536 KB Output is correct
9 Correct 847 ms 47024 KB Output is correct
10 Correct 1188 ms 47272 KB Output is correct
11 Correct 1530 ms 85392 KB Output is correct
12 Correct 1238 ms 79848 KB Output is correct
13 Correct 444 ms 1752 KB Output is correct
14 Correct 2 ms 1280 KB Output is correct
15 Correct 554 ms 1536 KB Output is correct
16 Correct 488 ms 1536 KB Output is correct
17 Correct 530 ms 1536 KB Output is correct
18 Correct 942 ms 17600 KB Output is correct
19 Correct 559 ms 1608 KB Output is correct
20 Correct 974 ms 18000 KB Output is correct
21 Correct 732 ms 1744 KB Output is correct
22 Correct 848 ms 1536 KB Output is correct
23 Correct 1038 ms 52840 KB Output is correct
24 Correct 1487 ms 52688 KB Output is correct
25 Correct 1918 ms 102632 KB Output is correct
26 Correct 1483 ms 89616 KB Output is correct
27 Correct 612 ms 2024 KB Output is correct
28 Correct 840 ms 1536 KB Output is correct
29 Correct 692 ms 1592 KB Output is correct
30 Correct 1720 ms 44504 KB Output is correct
31 Correct 696 ms 1448 KB Output is correct
32 Correct 1376 ms 37504 KB Output is correct
33 Correct 694 ms 1536 KB Output is correct
34 Correct 706 ms 1536 KB Output is correct
35 Correct 742 ms 1536 KB Output is correct
36 Correct 1178 ms 57856 KB Output is correct
37 Correct 1568 ms 58456 KB Output is correct
38 Correct 1954 ms 113344 KB Output is correct
39 Correct 1952 ms 103072 KB Output is correct
40 Correct 734 ms 2624 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 928 ms 1768 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 826 ms 1536 KB Output is correct
4 Correct 1225 ms 20192 KB Output is correct
5 Correct 66 ms 2016 KB Output is correct
6 Correct 1028 ms 5600 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Correct 979 ms 1792 KB Output is correct
9 Correct 1056 ms 1792 KB Output is correct
10 Correct 2013 ms 54880 KB Output is correct
11 Correct 1720 ms 57248 KB Output is correct
12 Correct 206 ms 1536 KB Output is correct
13 Correct 1455 ms 57840 KB Output is correct
14 Correct 876 ms 1632 KB Output is correct
15 Correct 4 ms 1280 KB Output is correct
16 Correct 862 ms 1536 KB Output is correct
17 Correct 1011 ms 1536 KB Output is correct
18 Correct 870 ms 1536 KB Output is correct
19 Correct 976 ms 1616 KB Output is correct
20 Correct 974 ms 1536 KB Output is correct
21 Correct 886 ms 1680 KB Output is correct
22 Correct 944 ms 1536 KB Output is correct
23 Correct 974 ms 2016 KB Output is correct
24 Correct 478 ms 1768 KB Output is correct
25 Correct 486 ms 1648 KB Output is correct
26 Correct 781 ms 24416 KB Output is correct
27 Correct 414 ms 1760 KB Output is correct
28 Correct 766 ms 17424 KB Output is correct
29 Correct 504 ms 1536 KB Output is correct
30 Correct 386 ms 1760 KB Output is correct
31 Correct 456 ms 1536 KB Output is correct
32 Correct 847 ms 47024 KB Output is correct
33 Correct 1188 ms 47272 KB Output is correct
34 Correct 1530 ms 85392 KB Output is correct
35 Correct 1238 ms 79848 KB Output is correct
36 Correct 444 ms 1752 KB Output is correct
37 Correct 2 ms 1280 KB Output is correct
38 Correct 554 ms 1536 KB Output is correct
39 Correct 488 ms 1536 KB Output is correct
40 Correct 530 ms 1536 KB Output is correct
41 Correct 942 ms 17600 KB Output is correct
42 Correct 559 ms 1608 KB Output is correct
43 Correct 974 ms 18000 KB Output is correct
44 Correct 732 ms 1744 KB Output is correct
45 Correct 848 ms 1536 KB Output is correct
46 Correct 1038 ms 52840 KB Output is correct
47 Correct 1487 ms 52688 KB Output is correct
48 Correct 1918 ms 102632 KB Output is correct
49 Correct 1483 ms 89616 KB Output is correct
50 Correct 612 ms 2024 KB Output is correct
51 Correct 840 ms 1536 KB Output is correct
52 Correct 692 ms 1592 KB Output is correct
53 Correct 1720 ms 44504 KB Output is correct
54 Correct 696 ms 1448 KB Output is correct
55 Correct 1376 ms 37504 KB Output is correct
56 Correct 694 ms 1536 KB Output is correct
57 Correct 706 ms 1536 KB Output is correct
58 Correct 742 ms 1536 KB Output is correct
59 Correct 1178 ms 57856 KB Output is correct
60 Correct 1568 ms 58456 KB Output is correct
61 Correct 1954 ms 113344 KB Output is correct
62 Correct 1952 ms 103072 KB Output is correct
63 Correct 734 ms 2624 KB Output is correct
64 Correct 1140 ms 2304 KB Output is correct
65 Correct 1804 ms 46928 KB Output is correct
66 Correct 1914 ms 40992 KB Output is correct
67 Correct 816 ms 2048 KB Output is correct
68 Correct 1094 ms 2304 KB Output is correct
69 Correct 2450 ms 111000 KB Output is correct
70 Correct 2177 ms 93944 KB Output is correct
71 Correct 1154 ms 12368 KB Output is correct
72 Correct 919 ms 2856 KB Output is correct