#include "Azer.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2005;
const int inf = mxN * 500;
vector<pair<int, int>> ad[mxN];
int n;
int dist[mxN];
int cur_dist = 0;
bool done[mxN];
void send_node(int u) {
for (int i = 0; i < 11; i++) {
SendA(u >> i & 1);
}
}
void send_weight(int w) {
w = min(w, 511);
for (int i = 0; i < 9; i++) {
SendA(w >> i & 1);
}
}
void relax(int u) {
for (auto [v, w] : ad[u]) {
dist[v] = min(dist[v], dist[u] + w);
}
}
pair<int, int> get_best() {
int who = -1, cur = inf;
for (int i = 0; i < n; i++) {
if (done[i]) continue;
if (dist[i] < cur) {
cur = dist[i];
who = i;
}
}
return {who, cur};
}
int need;
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
n = N;
for (int i = 0; i < A; i++) {
ad[U[i]].push_back({V[i], C[i]});
ad[V[i]].push_back({U[i], C[i]});
}
for (int i = 0; i < n; i++) {
dist[i] = inf;
}
dist[0] = 0;
done[0] = 1;
relax(0);
int need = n - 1;
if (need) send_weight(get_best().second);
}
bool rem() {
for (int i = 0; i < n; i++) {
if (!done[i]) return true;
}
return false;
}
int now = 1;
vector<int> store;
int cnt = 0;
void ReceiveA(bool x) {
store.push_back(x);
cnt++;
if (now == 1) {
if (cnt == 9) {
auto [who, cur] = get_best();
int val = 0;
for (int j = 0; j < 9; j++) {
if (store[j]) val |= (1 << j);
}
store.clear();
cnt = 0;
if (val == 511) {
send_node(who);
dist[who] = cur;
cur_dist = cur;
done[who] = true;
relax(who);
if (rem()) {
auto [w, cc] = get_best();
send_weight(cc - cur_dist);
now = 1;
}
} else {
cur_dist += val;
now = 0;
}
}
} else {
if (cnt == 11) {
int who = 0;
for (int j = 0; j < 11; j++) {
if (store[j]) who |= (1 << j);
}
store.clear();
cnt = 0;
dist[who] = cur_dist;
done[who] = true;
relax(who);
now = 1;
if (rem()) {
auto [w, cc] = get_best();
send_weight(cc - cur_dist);
}
}
}
}
std::vector<int> Answer() {
std::vector<int> ans(n);
for (int k = 0; k < n; ++k) {
ans[k] = dist[k];
}
return ans;
}
#include "Baijan.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2005;
const int inf = mxN * 500;
vector<pair<int, int>> add[mxN];
int nn;
int distt[mxN];
int cur_distt = 0;
bool donee[mxN];
void send_nodee(int u) {
for (int i = 0; i < 11; i++) {
SendB(u >> i & 1);
}
}
void send_weightt(int w) {
w = min(w, 511);
for (int i = 0; i < 9; i++) {
SendB(w >> i & 1);
}
}
void relaxx(int u) {
for (auto [v, w] : add[u]) {
distt[v] = min(distt[v], distt[u] + w);
}
}
pair<int, int> get_bestt() {
int who = -1, cur = inf;
for (int i = 0; i < nn; i++) {
if (donee[i]) continue;
if (distt[i] < cur) {
cur = distt[i];
who = i;
}
}
return {who, cur};
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
nn = N;
for (int i = 0; i < B; i++) {
add[S[i]].push_back({T[i], D[i]});
add[T[i]].push_back({S[i], D[i]});
}
for (int i = 0; i < nn; i++) {
distt[i] = inf;
}
distt[0] = 0;
donee[0] = 1;
relaxx(0);
}
int noww = 1;
vector<int> storee;
int cntt = 0;
void ReceiveB(bool y) {
cntt++;
storee.push_back(y);
if (noww) {
if (cntt == 9) {
auto [who, cur] = get_bestt();
int val = 0;
for (int j = 0; j < 9; j++) {
if (storee[j]) val |= (1 << j);
}
storee.clear();
cntt = 0;
if (val <= cur - cur_distt) {
send_weightt(511);
cur_distt += val;
noww = 0;
} else {
send_weightt(cur - cur_distt);
send_nodee(who);
cur_distt = cur;
distt[who] = cur;
relaxx(who);
donee[who] = true;
noww = 1;
}
}
} else {
if (cntt == 11) {
int who = 0;
for (int j = 0; j < 11; j++) {
if (storee[j]) who |= (1 << j);
}
storee.clear();
cntt = 0;
distt[who] = cur_distt;
donee[who] = true;
relaxx(who);
noww = 1;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
405 ms |
1052 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
386 ms |
1044 KB |
Output is correct |
4 |
Correct |
466 ms |
10364 KB |
Output is correct |
5 |
Correct |
13 ms |
920 KB |
Output is correct |
6 |
Correct |
385 ms |
2460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
664 KB |
Output is correct |
2 |
Correct |
357 ms |
876 KB |
Output is correct |
3 |
Correct |
354 ms |
932 KB |
Output is correct |
4 |
Correct |
530 ms |
27656 KB |
Output is correct |
5 |
Correct |
416 ms |
24200 KB |
Output is correct |
6 |
Correct |
54 ms |
664 KB |
Output is correct |
7 |
Correct |
470 ms |
24444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
395 ms |
860 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
356 ms |
792 KB |
Output is correct |
4 |
Correct |
390 ms |
876 KB |
Output is correct |
5 |
Correct |
313 ms |
872 KB |
Output is correct |
6 |
Correct |
407 ms |
864 KB |
Output is correct |
7 |
Correct |
393 ms |
872 KB |
Output is correct |
8 |
Correct |
402 ms |
980 KB |
Output is correct |
9 |
Correct |
403 ms |
788 KB |
Output is correct |
10 |
Correct |
362 ms |
1048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
816 KB |
Output is correct |
2 |
Correct |
163 ms |
796 KB |
Output is correct |
3 |
Correct |
197 ms |
13584 KB |
Output is correct |
4 |
Correct |
157 ms |
848 KB |
Output is correct |
5 |
Correct |
233 ms |
10088 KB |
Output is correct |
6 |
Correct |
159 ms |
836 KB |
Output is correct |
7 |
Correct |
155 ms |
664 KB |
Output is correct |
8 |
Correct |
150 ms |
916 KB |
Output is correct |
9 |
Correct |
284 ms |
18356 KB |
Output is correct |
10 |
Correct |
271 ms |
18484 KB |
Output is correct |
11 |
Correct |
382 ms |
35788 KB |
Output is correct |
12 |
Correct |
325 ms |
30784 KB |
Output is correct |
13 |
Correct |
172 ms |
664 KB |
Output is correct |
14 |
Correct |
1 ms |
664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
816 KB |
Output is correct |
2 |
Correct |
163 ms |
796 KB |
Output is correct |
3 |
Correct |
197 ms |
13584 KB |
Output is correct |
4 |
Correct |
157 ms |
848 KB |
Output is correct |
5 |
Correct |
233 ms |
10088 KB |
Output is correct |
6 |
Correct |
159 ms |
836 KB |
Output is correct |
7 |
Correct |
155 ms |
664 KB |
Output is correct |
8 |
Correct |
150 ms |
916 KB |
Output is correct |
9 |
Correct |
284 ms |
18356 KB |
Output is correct |
10 |
Correct |
271 ms |
18484 KB |
Output is correct |
11 |
Correct |
382 ms |
35788 KB |
Output is correct |
12 |
Correct |
325 ms |
30784 KB |
Output is correct |
13 |
Correct |
172 ms |
664 KB |
Output is correct |
14 |
Correct |
1 ms |
664 KB |
Output is correct |
15 |
Correct |
271 ms |
664 KB |
Output is correct |
16 |
Correct |
246 ms |
664 KB |
Output is correct |
17 |
Correct |
193 ms |
664 KB |
Output is correct |
18 |
Correct |
272 ms |
10176 KB |
Output is correct |
19 |
Correct |
220 ms |
920 KB |
Output is correct |
20 |
Correct |
249 ms |
10552 KB |
Output is correct |
21 |
Correct |
194 ms |
664 KB |
Output is correct |
22 |
Correct |
221 ms |
664 KB |
Output is correct |
23 |
Correct |
293 ms |
22412 KB |
Output is correct |
24 |
Correct |
292 ms |
22544 KB |
Output is correct |
25 |
Correct |
431 ms |
43664 KB |
Output is correct |
26 |
Correct |
391 ms |
36544 KB |
Output is correct |
27 |
Correct |
185 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
816 KB |
Output is correct |
2 |
Correct |
163 ms |
796 KB |
Output is correct |
3 |
Correct |
197 ms |
13584 KB |
Output is correct |
4 |
Correct |
157 ms |
848 KB |
Output is correct |
5 |
Correct |
233 ms |
10088 KB |
Output is correct |
6 |
Correct |
159 ms |
836 KB |
Output is correct |
7 |
Correct |
155 ms |
664 KB |
Output is correct |
8 |
Correct |
150 ms |
916 KB |
Output is correct |
9 |
Correct |
284 ms |
18356 KB |
Output is correct |
10 |
Correct |
271 ms |
18484 KB |
Output is correct |
11 |
Correct |
382 ms |
35788 KB |
Output is correct |
12 |
Correct |
325 ms |
30784 KB |
Output is correct |
13 |
Correct |
172 ms |
664 KB |
Output is correct |
14 |
Correct |
1 ms |
664 KB |
Output is correct |
15 |
Correct |
271 ms |
664 KB |
Output is correct |
16 |
Correct |
246 ms |
664 KB |
Output is correct |
17 |
Correct |
193 ms |
664 KB |
Output is correct |
18 |
Correct |
272 ms |
10176 KB |
Output is correct |
19 |
Correct |
220 ms |
920 KB |
Output is correct |
20 |
Correct |
249 ms |
10552 KB |
Output is correct |
21 |
Correct |
194 ms |
664 KB |
Output is correct |
22 |
Correct |
221 ms |
664 KB |
Output is correct |
23 |
Correct |
293 ms |
22412 KB |
Output is correct |
24 |
Correct |
292 ms |
22544 KB |
Output is correct |
25 |
Correct |
431 ms |
43664 KB |
Output is correct |
26 |
Correct |
391 ms |
36544 KB |
Output is correct |
27 |
Correct |
185 ms |
888 KB |
Output is correct |
28 |
Correct |
234 ms |
664 KB |
Output is correct |
29 |
Correct |
224 ms |
812 KB |
Output is correct |
30 |
Correct |
403 ms |
24220 KB |
Output is correct |
31 |
Correct |
252 ms |
788 KB |
Output is correct |
32 |
Correct |
369 ms |
21188 KB |
Output is correct |
33 |
Correct |
245 ms |
868 KB |
Output is correct |
34 |
Correct |
272 ms |
896 KB |
Output is correct |
35 |
Correct |
216 ms |
1156 KB |
Output is correct |
36 |
Correct |
400 ms |
25100 KB |
Output is correct |
37 |
Correct |
365 ms |
24980 KB |
Output is correct |
38 |
Correct |
525 ms |
49032 KB |
Output is correct |
39 |
Correct |
491 ms |
44176 KB |
Output is correct |
40 |
Correct |
225 ms |
1176 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
405 ms |
1052 KB |
Output is correct |
2 |
Correct |
0 ms |
664 KB |
Output is correct |
3 |
Correct |
386 ms |
1044 KB |
Output is correct |
4 |
Correct |
466 ms |
10364 KB |
Output is correct |
5 |
Correct |
13 ms |
920 KB |
Output is correct |
6 |
Correct |
385 ms |
2460 KB |
Output is correct |
7 |
Correct |
0 ms |
664 KB |
Output is correct |
8 |
Correct |
357 ms |
876 KB |
Output is correct |
9 |
Correct |
354 ms |
932 KB |
Output is correct |
10 |
Correct |
530 ms |
27656 KB |
Output is correct |
11 |
Correct |
416 ms |
24200 KB |
Output is correct |
12 |
Correct |
54 ms |
664 KB |
Output is correct |
13 |
Correct |
470 ms |
24444 KB |
Output is correct |
14 |
Correct |
395 ms |
860 KB |
Output is correct |
15 |
Correct |
0 ms |
664 KB |
Output is correct |
16 |
Correct |
356 ms |
792 KB |
Output is correct |
17 |
Correct |
390 ms |
876 KB |
Output is correct |
18 |
Correct |
313 ms |
872 KB |
Output is correct |
19 |
Correct |
407 ms |
864 KB |
Output is correct |
20 |
Correct |
393 ms |
872 KB |
Output is correct |
21 |
Correct |
402 ms |
980 KB |
Output is correct |
22 |
Correct |
403 ms |
788 KB |
Output is correct |
23 |
Correct |
362 ms |
1048 KB |
Output is correct |
24 |
Correct |
151 ms |
816 KB |
Output is correct |
25 |
Correct |
163 ms |
796 KB |
Output is correct |
26 |
Correct |
197 ms |
13584 KB |
Output is correct |
27 |
Correct |
157 ms |
848 KB |
Output is correct |
28 |
Correct |
233 ms |
10088 KB |
Output is correct |
29 |
Correct |
159 ms |
836 KB |
Output is correct |
30 |
Correct |
155 ms |
664 KB |
Output is correct |
31 |
Correct |
150 ms |
916 KB |
Output is correct |
32 |
Correct |
284 ms |
18356 KB |
Output is correct |
33 |
Correct |
271 ms |
18484 KB |
Output is correct |
34 |
Correct |
382 ms |
35788 KB |
Output is correct |
35 |
Correct |
325 ms |
30784 KB |
Output is correct |
36 |
Correct |
172 ms |
664 KB |
Output is correct |
37 |
Correct |
1 ms |
664 KB |
Output is correct |
38 |
Correct |
271 ms |
664 KB |
Output is correct |
39 |
Correct |
246 ms |
664 KB |
Output is correct |
40 |
Correct |
193 ms |
664 KB |
Output is correct |
41 |
Correct |
272 ms |
10176 KB |
Output is correct |
42 |
Correct |
220 ms |
920 KB |
Output is correct |
43 |
Correct |
249 ms |
10552 KB |
Output is correct |
44 |
Correct |
194 ms |
664 KB |
Output is correct |
45 |
Correct |
221 ms |
664 KB |
Output is correct |
46 |
Correct |
293 ms |
22412 KB |
Output is correct |
47 |
Correct |
292 ms |
22544 KB |
Output is correct |
48 |
Correct |
431 ms |
43664 KB |
Output is correct |
49 |
Correct |
391 ms |
36544 KB |
Output is correct |
50 |
Correct |
185 ms |
888 KB |
Output is correct |
51 |
Correct |
234 ms |
664 KB |
Output is correct |
52 |
Correct |
224 ms |
812 KB |
Output is correct |
53 |
Correct |
403 ms |
24220 KB |
Output is correct |
54 |
Correct |
252 ms |
788 KB |
Output is correct |
55 |
Correct |
369 ms |
21188 KB |
Output is correct |
56 |
Correct |
245 ms |
868 KB |
Output is correct |
57 |
Correct |
272 ms |
896 KB |
Output is correct |
58 |
Correct |
216 ms |
1156 KB |
Output is correct |
59 |
Correct |
400 ms |
25100 KB |
Output is correct |
60 |
Correct |
365 ms |
24980 KB |
Output is correct |
61 |
Correct |
525 ms |
49032 KB |
Output is correct |
62 |
Correct |
491 ms |
44176 KB |
Output is correct |
63 |
Correct |
225 ms |
1176 KB |
Output is correct |
64 |
Correct |
377 ms |
1216 KB |
Output is correct |
65 |
Correct |
510 ms |
26788 KB |
Output is correct |
66 |
Correct |
519 ms |
23496 KB |
Output is correct |
67 |
Correct |
374 ms |
1452 KB |
Output is correct |
68 |
Correct |
389 ms |
1196 KB |
Output is correct |
69 |
Correct |
611 ms |
48016 KB |
Output is correct |
70 |
Correct |
552 ms |
39668 KB |
Output is correct |
71 |
Correct |
382 ms |
5228 KB |
Output is correct |
72 |
Correct |
362 ms |
1176 KB |
Output is correct |