#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::high_resolution_clock
::now().time_since_epoch().count());
namespace {
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
struct edge {
int v, w;
edge(int v, int w): v(v), w(w) {}
bool operator < (const edge &o) const {
return w > o.w;
}
};
int N, last; bool coin;
int cnt, cur, prv, relaxed;
vector<vector<edge>> adj;
vector<int> dis;
vector<char> vis;
priority_queue<edge> pq;
void SendA1(int x, int k) {
while (k--) SendA(bool(x >> k & 1));
}
void Relax(int u) {
last = dis[u]; vis[u] = true;
for (edge e : adj[u])
if (cmin(dis[e.v], dis[u] + e.w))
pq.emplace(e.v, dis[e.v]);
while (pq.size()) {
auto p = pq.top();
if (dis[p.v] < p.w || vis[p.v])
pq.pop();
else break;
}
relaxed++;
}
void NewPhase() {
if (relaxed == N) return;
coin = rng() & 1; SendA(coin ^ 1);
if (coin) {
if (pq.size())
SendA1(pq.top().w - last, 9);
else SendA1(511, 9);
}
cnt = cur = prv = 0;
}
}
void InitA(int N, int A, vector<int> U,
vector<int> V, vector<int> C) {
::N = N; relaxed = 0;
dis.assign(N, 1e9);
adj.assign(N, vector <edge> ());
vis.assign(N, 0);
for (int i = 0; i < U.size(); i++) {
adj[U[i]].emplace_back(V[i], C[i]);
adj[V[i]].emplace_back(U[i], C[i]);
}
pq.emplace(0, dis[0] = 0);
Relax(0); NewPhase();
}
void ReceiveA(bool x) {
cur = (cur << 1) | x;
if (coin) {
if (++cnt == 1) {
if (x) {
SendA1(pq.top().v, 11);
Relax(pq.top().v); NewPhase();
}
} else if (cnt == 10) {
prv = cur; cur = 0;
} else if (cnt == 21) {
dis[cur] = last + prv;
Relax(cur); NewPhase();
}
} else {
if (++cnt == 9) {
if (pq.size() && cur + last > pq.top().w) {
SendA(0);
SendA1(pq.top().w - last, 9);
SendA1(pq.top().v, 11);
Relax(pq.top().v); NewPhase();
} else {
prv = cur; cur = 0; SendA(1);
}
} else if (cnt == 20) {
dis[cur] = last + prv;
Relax(cur); NewPhase();
}
}
}
vector<int> Answer() {
return dis;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
template <class X, class Y>
bool cmin(X &a, const Y &b) {
return a > b ? a = b, 1 : 0;
}
struct edge {
int v, w;
edge(int v, int w): v(v), w(w) {}
bool operator < (const edge &o) const {
return w > o.w;
}
};
int N, last; bool coin;
int cnt, cur, prv;
vector<vector<edge>> adj;
vector<int> dis;
vector<char> vis;
priority_queue<edge> pq;
void SendB1(int x, int k) {
while (k--) SendB(bool(x >> k & 1));
}
void Relax(int u) {
last = dis[u]; vis[u] = true;
for (edge e : adj[u])
if (cmin(dis[e.v], dis[u] + e.w))
pq.emplace(e.v, dis[e.v]);
while (pq.size()) {
auto p = pq.top();
if (dis[p.v] < p.w || vis[p.v])
pq.pop();
else break;
}
}
void NewPhase() {
cnt = cur = prv = 0;
}
}
void InitB(int N, int B, vector<int> S,
vector<int> T, vector<int> D) {
::N = N;
dis.assign(N, 1e9);
adj.assign(N, vector <edge> ());
vis.assign(N, 0);
for (int i = 0; i < S.size(); i++) {
adj[S[i]].emplace_back(T[i], D[i]);
adj[T[i]].emplace_back(S[i], D[i]);
}
pq.emplace(0, dis[0] = 0);
Relax(0); NewPhase();
}
void ReceiveB(bool y) {
if (++cnt == 1) {
coin = y;
if (y) {
if (pq.size())
SendB1(pq.top().w - last, 9);
else SendB1(511, 9);
}
return;
}
cur = (cur << 1) | y;
if (coin) {
if (cnt == 2) {
if (cur) {
SendB1(pq.top().v, 11);
Relax(pq.top().v); NewPhase();
}
} else if (cnt == 11) {
prv = cur; cur = 0;
} else if (cnt == 22) {
dis[cur] = last + prv;
Relax(cur); NewPhase();
}
} else {
if (cnt == 10) {
if (pq.size() && cur + last > pq.top().w) {
SendB(0);
SendB1(pq.top().w - last, 9);
SendB1(pq.top().v, 11);
Relax(pq.top().v); NewPhase();
} else {
prv = cur; cur = 0; SendB(1);
}
} else if (cnt == 21) {
dis[cur] = last + prv;
Relax(cur); NewPhase();
}
}
}
Compilation message
Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 0; i < U.size(); i++) {
| ~~^~~~~~~~~~
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | for (int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
784 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
536 ms |
784 KB |
Output is correct |
4 |
Correct |
571 ms |
10064 KB |
Output is correct |
5 |
Correct |
31 ms |
640 KB |
Output is correct |
6 |
Correct |
548 ms |
2100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
449 ms |
736 KB |
Output is correct |
3 |
Correct |
464 ms |
796 KB |
Output is correct |
4 |
Correct |
663 ms |
27532 KB |
Output is correct |
5 |
Correct |
655 ms |
24076 KB |
Output is correct |
6 |
Correct |
110 ms |
512 KB |
Output is correct |
7 |
Correct |
663 ms |
24200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
466 ms |
716 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
623 ms |
780 KB |
Output is correct |
4 |
Correct |
557 ms |
740 KB |
Output is correct |
5 |
Correct |
566 ms |
740 KB |
Output is correct |
6 |
Correct |
534 ms |
720 KB |
Output is correct |
7 |
Correct |
510 ms |
728 KB |
Output is correct |
8 |
Correct |
578 ms |
656 KB |
Output is correct |
9 |
Correct |
546 ms |
652 KB |
Output is correct |
10 |
Correct |
629 ms |
796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
760 KB |
Output is correct |
2 |
Correct |
214 ms |
644 KB |
Output is correct |
3 |
Correct |
299 ms |
13332 KB |
Output is correct |
4 |
Correct |
235 ms |
672 KB |
Output is correct |
5 |
Correct |
274 ms |
9920 KB |
Output is correct |
6 |
Correct |
262 ms |
656 KB |
Output is correct |
7 |
Correct |
243 ms |
684 KB |
Output is correct |
8 |
Correct |
249 ms |
644 KB |
Output is correct |
9 |
Correct |
313 ms |
18088 KB |
Output is correct |
10 |
Correct |
315 ms |
18132 KB |
Output is correct |
11 |
Correct |
472 ms |
35632 KB |
Output is correct |
12 |
Correct |
407 ms |
30568 KB |
Output is correct |
13 |
Correct |
226 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
760 KB |
Output is correct |
2 |
Correct |
214 ms |
644 KB |
Output is correct |
3 |
Correct |
299 ms |
13332 KB |
Output is correct |
4 |
Correct |
235 ms |
672 KB |
Output is correct |
5 |
Correct |
274 ms |
9920 KB |
Output is correct |
6 |
Correct |
262 ms |
656 KB |
Output is correct |
7 |
Correct |
243 ms |
684 KB |
Output is correct |
8 |
Correct |
249 ms |
644 KB |
Output is correct |
9 |
Correct |
313 ms |
18088 KB |
Output is correct |
10 |
Correct |
315 ms |
18132 KB |
Output is correct |
11 |
Correct |
472 ms |
35632 KB |
Output is correct |
12 |
Correct |
407 ms |
30568 KB |
Output is correct |
13 |
Correct |
226 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
320 ms |
640 KB |
Output is correct |
16 |
Correct |
264 ms |
512 KB |
Output is correct |
17 |
Correct |
299 ms |
552 KB |
Output is correct |
18 |
Correct |
385 ms |
10152 KB |
Output is correct |
19 |
Correct |
273 ms |
640 KB |
Output is correct |
20 |
Correct |
391 ms |
10188 KB |
Output is correct |
21 |
Correct |
258 ms |
712 KB |
Output is correct |
22 |
Correct |
290 ms |
640 KB |
Output is correct |
23 |
Correct |
454 ms |
21968 KB |
Output is correct |
24 |
Correct |
389 ms |
22192 KB |
Output is correct |
25 |
Correct |
650 ms |
43424 KB |
Output is correct |
26 |
Correct |
466 ms |
36756 KB |
Output is correct |
27 |
Correct |
156 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
760 KB |
Output is correct |
2 |
Correct |
214 ms |
644 KB |
Output is correct |
3 |
Correct |
299 ms |
13332 KB |
Output is correct |
4 |
Correct |
235 ms |
672 KB |
Output is correct |
5 |
Correct |
274 ms |
9920 KB |
Output is correct |
6 |
Correct |
262 ms |
656 KB |
Output is correct |
7 |
Correct |
243 ms |
684 KB |
Output is correct |
8 |
Correct |
249 ms |
644 KB |
Output is correct |
9 |
Correct |
313 ms |
18088 KB |
Output is correct |
10 |
Correct |
315 ms |
18132 KB |
Output is correct |
11 |
Correct |
472 ms |
35632 KB |
Output is correct |
12 |
Correct |
407 ms |
30568 KB |
Output is correct |
13 |
Correct |
226 ms |
640 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
320 ms |
640 KB |
Output is correct |
16 |
Correct |
264 ms |
512 KB |
Output is correct |
17 |
Correct |
299 ms |
552 KB |
Output is correct |
18 |
Correct |
385 ms |
10152 KB |
Output is correct |
19 |
Correct |
273 ms |
640 KB |
Output is correct |
20 |
Correct |
391 ms |
10188 KB |
Output is correct |
21 |
Correct |
258 ms |
712 KB |
Output is correct |
22 |
Correct |
290 ms |
640 KB |
Output is correct |
23 |
Correct |
454 ms |
21968 KB |
Output is correct |
24 |
Correct |
389 ms |
22192 KB |
Output is correct |
25 |
Correct |
650 ms |
43424 KB |
Output is correct |
26 |
Correct |
466 ms |
36756 KB |
Output is correct |
27 |
Correct |
156 ms |
640 KB |
Output is correct |
28 |
Correct |
356 ms |
680 KB |
Output is correct |
29 |
Correct |
336 ms |
640 KB |
Output is correct |
30 |
Correct |
529 ms |
23964 KB |
Output is correct |
31 |
Correct |
353 ms |
640 KB |
Output is correct |
32 |
Correct |
470 ms |
21012 KB |
Output is correct |
33 |
Correct |
388 ms |
712 KB |
Output is correct |
34 |
Correct |
409 ms |
740 KB |
Output is correct |
35 |
Correct |
333 ms |
744 KB |
Output is correct |
36 |
Correct |
583 ms |
24720 KB |
Output is correct |
37 |
Correct |
604 ms |
24636 KB |
Output is correct |
38 |
Correct |
681 ms |
48784 KB |
Output is correct |
39 |
Correct |
501 ms |
44028 KB |
Output is correct |
40 |
Correct |
392 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
486 ms |
784 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
536 ms |
784 KB |
Output is correct |
4 |
Correct |
571 ms |
10064 KB |
Output is correct |
5 |
Correct |
31 ms |
640 KB |
Output is correct |
6 |
Correct |
548 ms |
2100 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
449 ms |
736 KB |
Output is correct |
9 |
Correct |
464 ms |
796 KB |
Output is correct |
10 |
Correct |
663 ms |
27532 KB |
Output is correct |
11 |
Correct |
655 ms |
24076 KB |
Output is correct |
12 |
Correct |
110 ms |
512 KB |
Output is correct |
13 |
Correct |
663 ms |
24200 KB |
Output is correct |
14 |
Correct |
466 ms |
716 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
623 ms |
780 KB |
Output is correct |
17 |
Correct |
557 ms |
740 KB |
Output is correct |
18 |
Correct |
566 ms |
740 KB |
Output is correct |
19 |
Correct |
534 ms |
720 KB |
Output is correct |
20 |
Correct |
510 ms |
728 KB |
Output is correct |
21 |
Correct |
578 ms |
656 KB |
Output is correct |
22 |
Correct |
546 ms |
652 KB |
Output is correct |
23 |
Correct |
629 ms |
796 KB |
Output is correct |
24 |
Correct |
224 ms |
760 KB |
Output is correct |
25 |
Correct |
214 ms |
644 KB |
Output is correct |
26 |
Correct |
299 ms |
13332 KB |
Output is correct |
27 |
Correct |
235 ms |
672 KB |
Output is correct |
28 |
Correct |
274 ms |
9920 KB |
Output is correct |
29 |
Correct |
262 ms |
656 KB |
Output is correct |
30 |
Correct |
243 ms |
684 KB |
Output is correct |
31 |
Correct |
249 ms |
644 KB |
Output is correct |
32 |
Correct |
313 ms |
18088 KB |
Output is correct |
33 |
Correct |
315 ms |
18132 KB |
Output is correct |
34 |
Correct |
472 ms |
35632 KB |
Output is correct |
35 |
Correct |
407 ms |
30568 KB |
Output is correct |
36 |
Correct |
226 ms |
640 KB |
Output is correct |
37 |
Correct |
1 ms |
384 KB |
Output is correct |
38 |
Correct |
320 ms |
640 KB |
Output is correct |
39 |
Correct |
264 ms |
512 KB |
Output is correct |
40 |
Correct |
299 ms |
552 KB |
Output is correct |
41 |
Correct |
385 ms |
10152 KB |
Output is correct |
42 |
Correct |
273 ms |
640 KB |
Output is correct |
43 |
Correct |
391 ms |
10188 KB |
Output is correct |
44 |
Correct |
258 ms |
712 KB |
Output is correct |
45 |
Correct |
290 ms |
640 KB |
Output is correct |
46 |
Correct |
454 ms |
21968 KB |
Output is correct |
47 |
Correct |
389 ms |
22192 KB |
Output is correct |
48 |
Correct |
650 ms |
43424 KB |
Output is correct |
49 |
Correct |
466 ms |
36756 KB |
Output is correct |
50 |
Correct |
156 ms |
640 KB |
Output is correct |
51 |
Correct |
356 ms |
680 KB |
Output is correct |
52 |
Correct |
336 ms |
640 KB |
Output is correct |
53 |
Correct |
529 ms |
23964 KB |
Output is correct |
54 |
Correct |
353 ms |
640 KB |
Output is correct |
55 |
Correct |
470 ms |
21012 KB |
Output is correct |
56 |
Correct |
388 ms |
712 KB |
Output is correct |
57 |
Correct |
409 ms |
740 KB |
Output is correct |
58 |
Correct |
333 ms |
744 KB |
Output is correct |
59 |
Correct |
583 ms |
24720 KB |
Output is correct |
60 |
Correct |
604 ms |
24636 KB |
Output is correct |
61 |
Correct |
681 ms |
48784 KB |
Output is correct |
62 |
Correct |
501 ms |
44028 KB |
Output is correct |
63 |
Correct |
392 ms |
896 KB |
Output is correct |
64 |
Correct |
464 ms |
944 KB |
Output is correct |
65 |
Correct |
643 ms |
26480 KB |
Output is correct |
66 |
Correct |
677 ms |
23336 KB |
Output is correct |
67 |
Correct |
554 ms |
1020 KB |
Output is correct |
68 |
Correct |
581 ms |
924 KB |
Output is correct |
69 |
Correct |
693 ms |
47504 KB |
Output is correct |
70 |
Correct |
802 ms |
39544 KB |
Output is correct |
71 |
Correct |
464 ms |
4920 KB |
Output is correct |
72 |
Correct |
460 ms |
1168 KB |
Output is correct |