#include "Azer.h"
#include <vector>
#include <queue>
#define pii std::pair<int,int>
#define vec std::vector<pii >
#define pq std::priority_queue<pii >
namespace {
int N;
int vis[2000];
vec edge[2000];
int d[2000];
int buf[20];
int sz, r;
pq q;
int recon() {
int n = 0;
for (int i = 0; i < sz; ++i)
n += n + buf[i];
return n;
}
} // namespace
void _SendA(int n,int k) {
while (k--) {
SendA(n&1);
n >>= 1;
}
}
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) {
edge[U[i]].push_back({V[i],C[i]});
edge[V[i]].push_back({ U[i],C[i] });
}
for (int i = 0; i < N; ++i) q.push({ -1e9,i }), d[i] = 1e9;
vis[0] = 1; d[0] = 0;
for (auto p : edge[0]) {
int v = p.first;
int c = p.second;
d[v] = c;
q.push({-d[v],v});
}
int da=-q.top().first;
if (da > 500) da = 510;
_SendA(da, 9); sz = r = 9;
buf[18] = 0;
}
void ReceiveA(bool x) {
buf[--r]=x;
if (r == 0) {
int v;
if (sz == 9) {
int db = recon();
v = q.top().second;
int da = d[v] - d[buf[18]];
if (da <= db) {
_SendA(v,11);
q.pop();
//go inq
}
else {
buf[19] = db;
r = sz = 11;
return;
}
}
else {//sync v
v= recon();
d[v] = d[buf[18]] + buf[19];
//go inq
}
//inq
vis[v] = 1;
for (auto p : edge[v]) {
int nxt = p.first;
int c = p.second;
if (d[nxt] > d[v] + c) {
d[nxt] = d[v] + c;
q.push({ -d[nxt],nxt });
}
}
while (q.size() && vis[q.top().second]) q.pop();//q empty chk??
if (q.size()) {
int da = -q.top().first;
int diff = da - d[v];
if (diff > 500) diff = 510;
_SendA(diff, 9);
r = sz = 9;
buf[18] = v;
}
}
}
std::vector<int> Answer() {
std::vector<int> ans(N);
for (int i = 0; i < N; ++i) ans[i] = d[i];
return ans;
}
#include "Baijan.h"
#include <vector>
#include <queue>
#define pii std::pair<int,int>
#define vec std::vector<pii >
#define pq std::priority_queue<pii >
namespace {
int N;
int vis[2000];
vec edge[2000];
int d[2000];
int sz, r;
int buf[20];
pq q;
int recon() {
int n = 0;
for (int i = 0; i < sz; ++i) n += n + buf[i];
return n;
}
} // namespace
void _SendB(int n, int k) {
while (k--) {
SendB(n & 1);
n >>= 1;
}
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
std::vector<int> D) {
::N = N;
for (int i = 0; i < B; ++i) {
edge[S[i]].push_back({T[i],D[i]});
edge[T[i]].push_back({ S[i],D[i] });
}
for (int i = 0; i < N; ++i) q.push({ -1e9,i }), d[i] = 1e9;
vis[0] = 1; d[0] = 0;
for (auto p : edge[0]) {
int v = p.first;
int c = p.second;
d[v] = c;
q.push({ -d[v],v });
}
int db = -q.top().first;
if (db > 500) db = 510;
_SendB(db, 9); sz = r = 9; buf[18] = 0;
}
void ReceiveB(bool y) {
buf[--r] = y;
if (r == 0) {
int v;
if (sz == 9) {
int da = recon();
v = q.top().second;
int db = d[v]-d[buf[18]];
if (da > db) {
_SendB(v, 11);
q.pop();
//go inq
}
else {
buf[19] = da;
r = sz = 11;
return;
}
}
else {//sync v
v = recon();
d[v] = d[buf[18]] + buf[19];
//go inq
}
//inq
vis[v] = 1;
for (auto p : edge[v]) {
int nxt = p.first;
int c = p.second;
if (d[nxt] > d[v] + c) {
d[nxt] = d[v] + c;
q.push({ -d[nxt],nxt });
}
}
while (q.size() && vis[q.top().second]) q.pop();//q empty chk??
if (q.size()) {
int db = -q.top().first;
int diff = db - d[v];
if (diff > 500) diff = 510;
_SendB(diff, 9);
r = sz = 9;
buf[18] = v;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1196 ms |
1592 KB |
Output is correct |
2 |
Correct |
4 ms |
1192 KB |
Output is correct |
3 |
Correct |
1148 ms |
1760 KB |
Output is correct |
4 |
Correct |
1346 ms |
20152 KB |
Output is correct |
5 |
Correct |
50 ms |
1440 KB |
Output is correct |
6 |
Correct |
1228 ms |
4304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1088 KB |
Output is correct |
2 |
Correct |
1094 ms |
1760 KB |
Output is correct |
3 |
Correct |
928 ms |
1752 KB |
Output is correct |
4 |
Correct |
1464 ms |
55128 KB |
Output is correct |
5 |
Correct |
1588 ms |
48448 KB |
Output is correct |
6 |
Correct |
224 ms |
1232 KB |
Output is correct |
7 |
Correct |
1560 ms |
48512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1162 ms |
1848 KB |
Output is correct |
2 |
Correct |
8 ms |
992 KB |
Output is correct |
3 |
Correct |
932 ms |
1528 KB |
Output is correct |
4 |
Correct |
764 ms |
1760 KB |
Output is correct |
5 |
Correct |
1018 ms |
1784 KB |
Output is correct |
6 |
Correct |
1130 ms |
1712 KB |
Output is correct |
7 |
Correct |
1178 ms |
1528 KB |
Output is correct |
8 |
Correct |
796 ms |
1608 KB |
Output is correct |
9 |
Correct |
1050 ms |
1760 KB |
Output is correct |
10 |
Correct |
986 ms |
1768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
1760 KB |
Output is correct |
2 |
Correct |
482 ms |
1768 KB |
Output is correct |
3 |
Correct |
724 ms |
23680 KB |
Output is correct |
4 |
Correct |
452 ms |
1880 KB |
Output is correct |
5 |
Correct |
686 ms |
17216 KB |
Output is correct |
6 |
Correct |
380 ms |
1656 KB |
Output is correct |
7 |
Correct |
372 ms |
1888 KB |
Output is correct |
8 |
Correct |
530 ms |
1576 KB |
Output is correct |
9 |
Correct |
886 ms |
35888 KB |
Output is correct |
10 |
Correct |
718 ms |
36056 KB |
Output is correct |
11 |
Correct |
1100 ms |
61248 KB |
Output is correct |
12 |
Correct |
1020 ms |
53904 KB |
Output is correct |
13 |
Correct |
418 ms |
2112 KB |
Output is correct |
14 |
Correct |
4 ms |
1248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
1760 KB |
Output is correct |
2 |
Correct |
482 ms |
1768 KB |
Output is correct |
3 |
Correct |
724 ms |
23680 KB |
Output is correct |
4 |
Correct |
452 ms |
1880 KB |
Output is correct |
5 |
Correct |
686 ms |
17216 KB |
Output is correct |
6 |
Correct |
380 ms |
1656 KB |
Output is correct |
7 |
Correct |
372 ms |
1888 KB |
Output is correct |
8 |
Correct |
530 ms |
1576 KB |
Output is correct |
9 |
Correct |
886 ms |
35888 KB |
Output is correct |
10 |
Correct |
718 ms |
36056 KB |
Output is correct |
11 |
Correct |
1100 ms |
61248 KB |
Output is correct |
12 |
Correct |
1020 ms |
53904 KB |
Output is correct |
13 |
Correct |
418 ms |
2112 KB |
Output is correct |
14 |
Correct |
4 ms |
1248 KB |
Output is correct |
15 |
Correct |
572 ms |
1832 KB |
Output is correct |
16 |
Correct |
484 ms |
1888 KB |
Output is correct |
17 |
Correct |
434 ms |
1576 KB |
Output is correct |
18 |
Correct |
779 ms |
17600 KB |
Output is correct |
19 |
Correct |
501 ms |
1600 KB |
Output is correct |
20 |
Correct |
752 ms |
18072 KB |
Output is correct |
21 |
Correct |
660 ms |
1856 KB |
Output is correct |
22 |
Correct |
374 ms |
1824 KB |
Output is correct |
23 |
Correct |
900 ms |
44080 KB |
Output is correct |
24 |
Correct |
918 ms |
43944 KB |
Output is correct |
25 |
Correct |
1334 ms |
74792 KB |
Output is correct |
26 |
Correct |
1206 ms |
64120 KB |
Output is correct |
27 |
Correct |
500 ms |
1856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
1760 KB |
Output is correct |
2 |
Correct |
482 ms |
1768 KB |
Output is correct |
3 |
Correct |
724 ms |
23680 KB |
Output is correct |
4 |
Correct |
452 ms |
1880 KB |
Output is correct |
5 |
Correct |
686 ms |
17216 KB |
Output is correct |
6 |
Correct |
380 ms |
1656 KB |
Output is correct |
7 |
Correct |
372 ms |
1888 KB |
Output is correct |
8 |
Correct |
530 ms |
1576 KB |
Output is correct |
9 |
Correct |
886 ms |
35888 KB |
Output is correct |
10 |
Correct |
718 ms |
36056 KB |
Output is correct |
11 |
Correct |
1100 ms |
61248 KB |
Output is correct |
12 |
Correct |
1020 ms |
53904 KB |
Output is correct |
13 |
Correct |
418 ms |
2112 KB |
Output is correct |
14 |
Correct |
4 ms |
1248 KB |
Output is correct |
15 |
Correct |
572 ms |
1832 KB |
Output is correct |
16 |
Correct |
484 ms |
1888 KB |
Output is correct |
17 |
Correct |
434 ms |
1576 KB |
Output is correct |
18 |
Correct |
779 ms |
17600 KB |
Output is correct |
19 |
Correct |
501 ms |
1600 KB |
Output is correct |
20 |
Correct |
752 ms |
18072 KB |
Output is correct |
21 |
Correct |
660 ms |
1856 KB |
Output is correct |
22 |
Correct |
374 ms |
1824 KB |
Output is correct |
23 |
Correct |
900 ms |
44080 KB |
Output is correct |
24 |
Correct |
918 ms |
43944 KB |
Output is correct |
25 |
Correct |
1334 ms |
74792 KB |
Output is correct |
26 |
Correct |
1206 ms |
64120 KB |
Output is correct |
27 |
Correct |
500 ms |
1856 KB |
Output is correct |
28 |
Correct |
658 ms |
1800 KB |
Output is correct |
29 |
Correct |
566 ms |
1712 KB |
Output is correct |
30 |
Correct |
1042 ms |
42000 KB |
Output is correct |
31 |
Correct |
646 ms |
1792 KB |
Output is correct |
32 |
Correct |
1044 ms |
37496 KB |
Output is correct |
33 |
Correct |
610 ms |
1712 KB |
Output is correct |
34 |
Correct |
647 ms |
2016 KB |
Output is correct |
35 |
Correct |
652 ms |
1728 KB |
Output is correct |
36 |
Correct |
994 ms |
49064 KB |
Output is correct |
37 |
Correct |
950 ms |
49128 KB |
Output is correct |
38 |
Correct |
1656 ms |
85320 KB |
Output is correct |
39 |
Correct |
1248 ms |
78464 KB |
Output is correct |
40 |
Correct |
768 ms |
2136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1196 ms |
1592 KB |
Output is correct |
2 |
Correct |
4 ms |
1192 KB |
Output is correct |
3 |
Correct |
1148 ms |
1760 KB |
Output is correct |
4 |
Correct |
1346 ms |
20152 KB |
Output is correct |
5 |
Correct |
50 ms |
1440 KB |
Output is correct |
6 |
Correct |
1228 ms |
4304 KB |
Output is correct |
7 |
Correct |
6 ms |
1088 KB |
Output is correct |
8 |
Correct |
1094 ms |
1760 KB |
Output is correct |
9 |
Correct |
928 ms |
1752 KB |
Output is correct |
10 |
Correct |
1464 ms |
55128 KB |
Output is correct |
11 |
Correct |
1588 ms |
48448 KB |
Output is correct |
12 |
Correct |
224 ms |
1232 KB |
Output is correct |
13 |
Correct |
1560 ms |
48512 KB |
Output is correct |
14 |
Correct |
1162 ms |
1848 KB |
Output is correct |
15 |
Correct |
8 ms |
992 KB |
Output is correct |
16 |
Correct |
932 ms |
1528 KB |
Output is correct |
17 |
Correct |
764 ms |
1760 KB |
Output is correct |
18 |
Correct |
1018 ms |
1784 KB |
Output is correct |
19 |
Correct |
1130 ms |
1712 KB |
Output is correct |
20 |
Correct |
1178 ms |
1528 KB |
Output is correct |
21 |
Correct |
796 ms |
1608 KB |
Output is correct |
22 |
Correct |
1050 ms |
1760 KB |
Output is correct |
23 |
Correct |
986 ms |
1768 KB |
Output is correct |
24 |
Correct |
486 ms |
1760 KB |
Output is correct |
25 |
Correct |
482 ms |
1768 KB |
Output is correct |
26 |
Correct |
724 ms |
23680 KB |
Output is correct |
27 |
Correct |
452 ms |
1880 KB |
Output is correct |
28 |
Correct |
686 ms |
17216 KB |
Output is correct |
29 |
Correct |
380 ms |
1656 KB |
Output is correct |
30 |
Correct |
372 ms |
1888 KB |
Output is correct |
31 |
Correct |
530 ms |
1576 KB |
Output is correct |
32 |
Correct |
886 ms |
35888 KB |
Output is correct |
33 |
Correct |
718 ms |
36056 KB |
Output is correct |
34 |
Correct |
1100 ms |
61248 KB |
Output is correct |
35 |
Correct |
1020 ms |
53904 KB |
Output is correct |
36 |
Correct |
418 ms |
2112 KB |
Output is correct |
37 |
Correct |
4 ms |
1248 KB |
Output is correct |
38 |
Correct |
572 ms |
1832 KB |
Output is correct |
39 |
Correct |
484 ms |
1888 KB |
Output is correct |
40 |
Correct |
434 ms |
1576 KB |
Output is correct |
41 |
Correct |
779 ms |
17600 KB |
Output is correct |
42 |
Correct |
501 ms |
1600 KB |
Output is correct |
43 |
Correct |
752 ms |
18072 KB |
Output is correct |
44 |
Correct |
660 ms |
1856 KB |
Output is correct |
45 |
Correct |
374 ms |
1824 KB |
Output is correct |
46 |
Correct |
900 ms |
44080 KB |
Output is correct |
47 |
Correct |
918 ms |
43944 KB |
Output is correct |
48 |
Correct |
1334 ms |
74792 KB |
Output is correct |
49 |
Correct |
1206 ms |
64120 KB |
Output is correct |
50 |
Correct |
500 ms |
1856 KB |
Output is correct |
51 |
Correct |
658 ms |
1800 KB |
Output is correct |
52 |
Correct |
566 ms |
1712 KB |
Output is correct |
53 |
Correct |
1042 ms |
42000 KB |
Output is correct |
54 |
Correct |
646 ms |
1792 KB |
Output is correct |
55 |
Correct |
1044 ms |
37496 KB |
Output is correct |
56 |
Correct |
610 ms |
1712 KB |
Output is correct |
57 |
Correct |
647 ms |
2016 KB |
Output is correct |
58 |
Correct |
652 ms |
1728 KB |
Output is correct |
59 |
Correct |
994 ms |
49064 KB |
Output is correct |
60 |
Correct |
950 ms |
49128 KB |
Output is correct |
61 |
Correct |
1656 ms |
85320 KB |
Output is correct |
62 |
Correct |
1248 ms |
78464 KB |
Output is correct |
63 |
Correct |
768 ms |
2136 KB |
Output is correct |
64 |
Correct |
818 ms |
2416 KB |
Output is correct |
65 |
Correct |
1390 ms |
47136 KB |
Output is correct |
66 |
Correct |
1152 ms |
40760 KB |
Output is correct |
67 |
Correct |
1050 ms |
2072 KB |
Output is correct |
68 |
Correct |
1140 ms |
2016 KB |
Output is correct |
69 |
Correct |
1924 ms |
83328 KB |
Output is correct |
70 |
Correct |
1924 ms |
68112 KB |
Output is correct |
71 |
Correct |
878 ms |
9136 KB |
Output is correct |
72 |
Correct |
776 ms |
2272 KB |
Output is correct |