#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 = 1e9 + 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 = 1e9 + 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);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
502 ms |
780 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
604 ms |
772 KB |
Output is correct |
4 |
Correct |
695 ms |
10104 KB |
Output is correct |
5 |
Correct |
33 ms |
920 KB |
Output is correct |
6 |
Correct |
675 ms |
2572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
640 KB |
Output is correct |
2 |
Correct |
609 ms |
736 KB |
Output is correct |
3 |
Correct |
475 ms |
800 KB |
Output is correct |
4 |
Correct |
903 ms |
27520 KB |
Output is correct |
5 |
Correct |
984 ms |
24412 KB |
Output is correct |
6 |
Correct |
71 ms |
712 KB |
Output is correct |
7 |
Correct |
874 ms |
24592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
598 ms |
708 KB |
Output is correct |
2 |
Correct |
2 ms |
644 KB |
Output is correct |
3 |
Correct |
488 ms |
644 KB |
Output is correct |
4 |
Correct |
554 ms |
728 KB |
Output is correct |
5 |
Correct |
607 ms |
740 KB |
Output is correct |
6 |
Correct |
434 ms |
716 KB |
Output is correct |
7 |
Correct |
567 ms |
728 KB |
Output is correct |
8 |
Correct |
488 ms |
656 KB |
Output is correct |
9 |
Correct |
482 ms |
764 KB |
Output is correct |
10 |
Correct |
585 ms |
776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
672 KB |
Output is correct |
2 |
Correct |
249 ms |
644 KB |
Output is correct |
3 |
Correct |
359 ms |
13392 KB |
Output is correct |
4 |
Correct |
300 ms |
640 KB |
Output is correct |
5 |
Correct |
230 ms |
10092 KB |
Output is correct |
6 |
Correct |
220 ms |
644 KB |
Output is correct |
7 |
Correct |
253 ms |
640 KB |
Output is correct |
8 |
Correct |
194 ms |
716 KB |
Output is correct |
9 |
Correct |
501 ms |
19420 KB |
Output is correct |
10 |
Correct |
454 ms |
19680 KB |
Output is correct |
11 |
Correct |
659 ms |
38556 KB |
Output is correct |
12 |
Correct |
607 ms |
35884 KB |
Output is correct |
13 |
Correct |
269 ms |
644 KB |
Output is correct |
14 |
Correct |
2 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
672 KB |
Output is correct |
2 |
Correct |
249 ms |
644 KB |
Output is correct |
3 |
Correct |
359 ms |
13392 KB |
Output is correct |
4 |
Correct |
300 ms |
640 KB |
Output is correct |
5 |
Correct |
230 ms |
10092 KB |
Output is correct |
6 |
Correct |
220 ms |
644 KB |
Output is correct |
7 |
Correct |
253 ms |
640 KB |
Output is correct |
8 |
Correct |
194 ms |
716 KB |
Output is correct |
9 |
Correct |
501 ms |
19420 KB |
Output is correct |
10 |
Correct |
454 ms |
19680 KB |
Output is correct |
11 |
Correct |
659 ms |
38556 KB |
Output is correct |
12 |
Correct |
607 ms |
35884 KB |
Output is correct |
13 |
Correct |
269 ms |
644 KB |
Output is correct |
14 |
Correct |
2 ms |
640 KB |
Output is correct |
15 |
Correct |
331 ms |
680 KB |
Output is correct |
16 |
Correct |
279 ms |
700 KB |
Output is correct |
17 |
Correct |
202 ms |
644 KB |
Output is correct |
18 |
Correct |
412 ms |
10108 KB |
Output is correct |
19 |
Correct |
324 ms |
708 KB |
Output is correct |
20 |
Correct |
455 ms |
10352 KB |
Output is correct |
21 |
Correct |
311 ms |
724 KB |
Output is correct |
22 |
Correct |
300 ms |
640 KB |
Output is correct |
23 |
Correct |
571 ms |
22408 KB |
Output is correct |
24 |
Correct |
532 ms |
22408 KB |
Output is correct |
25 |
Correct |
707 ms |
44304 KB |
Output is correct |
26 |
Correct |
705 ms |
40620 KB |
Output is correct |
27 |
Correct |
267 ms |
872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
250 ms |
672 KB |
Output is correct |
2 |
Correct |
249 ms |
644 KB |
Output is correct |
3 |
Correct |
359 ms |
13392 KB |
Output is correct |
4 |
Correct |
300 ms |
640 KB |
Output is correct |
5 |
Correct |
230 ms |
10092 KB |
Output is correct |
6 |
Correct |
220 ms |
644 KB |
Output is correct |
7 |
Correct |
253 ms |
640 KB |
Output is correct |
8 |
Correct |
194 ms |
716 KB |
Output is correct |
9 |
Correct |
501 ms |
19420 KB |
Output is correct |
10 |
Correct |
454 ms |
19680 KB |
Output is correct |
11 |
Correct |
659 ms |
38556 KB |
Output is correct |
12 |
Correct |
607 ms |
35884 KB |
Output is correct |
13 |
Correct |
269 ms |
644 KB |
Output is correct |
14 |
Correct |
2 ms |
640 KB |
Output is correct |
15 |
Correct |
331 ms |
680 KB |
Output is correct |
16 |
Correct |
279 ms |
700 KB |
Output is correct |
17 |
Correct |
202 ms |
644 KB |
Output is correct |
18 |
Correct |
412 ms |
10108 KB |
Output is correct |
19 |
Correct |
324 ms |
708 KB |
Output is correct |
20 |
Correct |
455 ms |
10352 KB |
Output is correct |
21 |
Correct |
311 ms |
724 KB |
Output is correct |
22 |
Correct |
300 ms |
640 KB |
Output is correct |
23 |
Correct |
571 ms |
22408 KB |
Output is correct |
24 |
Correct |
532 ms |
22408 KB |
Output is correct |
25 |
Correct |
707 ms |
44304 KB |
Output is correct |
26 |
Correct |
705 ms |
40620 KB |
Output is correct |
27 |
Correct |
267 ms |
872 KB |
Output is correct |
28 |
Correct |
424 ms |
696 KB |
Output is correct |
29 |
Correct |
273 ms |
640 KB |
Output is correct |
30 |
Correct |
716 ms |
24196 KB |
Output is correct |
31 |
Correct |
301 ms |
764 KB |
Output is correct |
32 |
Correct |
598 ms |
21156 KB |
Output is correct |
33 |
Correct |
418 ms |
724 KB |
Output is correct |
34 |
Correct |
392 ms |
748 KB |
Output is correct |
35 |
Correct |
375 ms |
760 KB |
Output is correct |
36 |
Correct |
671 ms |
25096 KB |
Output is correct |
37 |
Correct |
657 ms |
25064 KB |
Output is correct |
38 |
Correct |
894 ms |
49488 KB |
Output is correct |
39 |
Correct |
859 ms |
47288 KB |
Output is correct |
40 |
Correct |
412 ms |
1036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
502 ms |
780 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
3 |
Correct |
604 ms |
772 KB |
Output is correct |
4 |
Correct |
695 ms |
10104 KB |
Output is correct |
5 |
Correct |
33 ms |
920 KB |
Output is correct |
6 |
Correct |
675 ms |
2572 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
609 ms |
736 KB |
Output is correct |
9 |
Correct |
475 ms |
800 KB |
Output is correct |
10 |
Correct |
903 ms |
27520 KB |
Output is correct |
11 |
Correct |
984 ms |
24412 KB |
Output is correct |
12 |
Correct |
71 ms |
712 KB |
Output is correct |
13 |
Correct |
874 ms |
24592 KB |
Output is correct |
14 |
Correct |
598 ms |
708 KB |
Output is correct |
15 |
Correct |
2 ms |
644 KB |
Output is correct |
16 |
Correct |
488 ms |
644 KB |
Output is correct |
17 |
Correct |
554 ms |
728 KB |
Output is correct |
18 |
Correct |
607 ms |
740 KB |
Output is correct |
19 |
Correct |
434 ms |
716 KB |
Output is correct |
20 |
Correct |
567 ms |
728 KB |
Output is correct |
21 |
Correct |
488 ms |
656 KB |
Output is correct |
22 |
Correct |
482 ms |
764 KB |
Output is correct |
23 |
Correct |
585 ms |
776 KB |
Output is correct |
24 |
Correct |
250 ms |
672 KB |
Output is correct |
25 |
Correct |
249 ms |
644 KB |
Output is correct |
26 |
Correct |
359 ms |
13392 KB |
Output is correct |
27 |
Correct |
300 ms |
640 KB |
Output is correct |
28 |
Correct |
230 ms |
10092 KB |
Output is correct |
29 |
Correct |
220 ms |
644 KB |
Output is correct |
30 |
Correct |
253 ms |
640 KB |
Output is correct |
31 |
Correct |
194 ms |
716 KB |
Output is correct |
32 |
Correct |
501 ms |
19420 KB |
Output is correct |
33 |
Correct |
454 ms |
19680 KB |
Output is correct |
34 |
Correct |
659 ms |
38556 KB |
Output is correct |
35 |
Correct |
607 ms |
35884 KB |
Output is correct |
36 |
Correct |
269 ms |
644 KB |
Output is correct |
37 |
Correct |
2 ms |
640 KB |
Output is correct |
38 |
Correct |
331 ms |
680 KB |
Output is correct |
39 |
Correct |
279 ms |
700 KB |
Output is correct |
40 |
Correct |
202 ms |
644 KB |
Output is correct |
41 |
Correct |
412 ms |
10108 KB |
Output is correct |
42 |
Correct |
324 ms |
708 KB |
Output is correct |
43 |
Correct |
455 ms |
10352 KB |
Output is correct |
44 |
Correct |
311 ms |
724 KB |
Output is correct |
45 |
Correct |
300 ms |
640 KB |
Output is correct |
46 |
Correct |
571 ms |
22408 KB |
Output is correct |
47 |
Correct |
532 ms |
22408 KB |
Output is correct |
48 |
Correct |
707 ms |
44304 KB |
Output is correct |
49 |
Correct |
705 ms |
40620 KB |
Output is correct |
50 |
Correct |
267 ms |
872 KB |
Output is correct |
51 |
Correct |
424 ms |
696 KB |
Output is correct |
52 |
Correct |
273 ms |
640 KB |
Output is correct |
53 |
Correct |
716 ms |
24196 KB |
Output is correct |
54 |
Correct |
301 ms |
764 KB |
Output is correct |
55 |
Correct |
598 ms |
21156 KB |
Output is correct |
56 |
Correct |
418 ms |
724 KB |
Output is correct |
57 |
Correct |
392 ms |
748 KB |
Output is correct |
58 |
Correct |
375 ms |
760 KB |
Output is correct |
59 |
Correct |
671 ms |
25096 KB |
Output is correct |
60 |
Correct |
657 ms |
25064 KB |
Output is correct |
61 |
Correct |
894 ms |
49488 KB |
Output is correct |
62 |
Correct |
859 ms |
47288 KB |
Output is correct |
63 |
Correct |
412 ms |
1036 KB |
Output is correct |
64 |
Correct |
621 ms |
944 KB |
Output is correct |
65 |
Correct |
725 ms |
26492 KB |
Output is correct |
66 |
Correct |
783 ms |
23408 KB |
Output is correct |
67 |
Correct |
587 ms |
924 KB |
Output is correct |
68 |
Correct |
523 ms |
920 KB |
Output is correct |
69 |
Correct |
1078 ms |
48344 KB |
Output is correct |
70 |
Correct |
963 ms |
41428 KB |
Output is correct |
71 |
Correct |
587 ms |
5524 KB |
Output is correct |
72 |
Correct |
583 ms |
1324 KB |
Output is correct |