// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
namespace {
const int NLOG = 11, CLOG = 9;
const int INF = 1000000005;
const int FINF = (1 << CLOG) - 2;
const int MAXN = 200005;
int n, m;
vii adj[MAXN];
queue<bool> qu;
int vis[MAXN];
vi dist;
bool waitDist;
int pd;
int get(int bits) {
int x = 0;
REP (i, 0, bits) {
x += qu.front() << i;
qu.pop();
}
return x;
}
void send(int x, int bits) {
REP (i, 0, bits) {
SendA(x >> i & 1);
}
}
ii dijkstra() {
int u = -1, d = INF + 1;
REP (i, 0, n) {
if (vis[i]) continue;
if (mnto(d, dist[i])) {
u = i;
}
}
return {u, d};
}
void relax(int u) {
for (auto [v, w] : adj[u]) {
mnto(dist[v], dist[u] + w);
}
}
}
void InitA(int N, int A, vi U, vi V, vi C) {
n = N; m = A;
REP (i, 0, m) {
adj[U[i]].pb({V[i], C[i]});
adj[V[i]].pb({U[i], C[i]});
}
dist = vi(n, INF);
dist[0] = 0;
auto [u, d] = dijkstra();
send(d, CLOG);
waitDist = 1;
}
void ReceiveA(bool x) {
qu.push(x);
bool found = 0;
if (waitDist) {
if (qu.size() == CLOG) {
int nd = get(CLOG) + pd;
auto [u, d] = dijkstra();
cerr << "A " << nd << ' ' << d << '\n';
if (d < nd) {
send(u, NLOG);
pd = d;
vis[u] = 1;
found = 1;
relax(u);
} else {
waitDist = 0;
pd = nd;
}
}
} else {
if (qu.size() == NLOG) {
int u = get(NLOG);
cerr << "A u " << u << '\n';
dist[u] = pd;
relax(u);
vis[u] = 1;
waitDist = 1;
found = 1;
}
}
if (found) {
auto [u, d] = dijkstra();
cerr << " A " << u << ' ' << d << '\n';
if (u != -1) {
send(min(d - pd, FINF), CLOG);
}
}
}
vi Answer() {
return dist;
}
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
namespace {
const int NLOG = 11, CLOG = 9;
const int INF = 1000000005;
const int FINF = (1 << CLOG) - 2;
const int MAXN = 200005;
int n, m;
vii adj[MAXN];
queue<bool> qu;
int vis[MAXN];
vi dist;
bool waitDist;
int pd;
int get(int bits) {
int x = 0;
REP (i, 0, bits) {
x += qu.front() << i;
qu.pop();
}
return x;
}
void send(int x, int bits) {
REP (i, 0, bits) {
SendB(x >> i & 1);
}
}
ii dijkstra() {
int u = -1, d = INF + 1;
REP (i, 0, n) {
if (vis[i]) continue;
if (mnto(d, dist[i])) {
u = i;
}
}
return {u, d};
}
void relax(int u) {
for (auto [v, w] : adj[u]) {
mnto(dist[v], dist[u] + w);
}
}
}
void InitB(int N, int A, vi U, vi V, vi C) {
n = N; m = A;
REP (i, 0, m) {
adj[U[i]].pb({V[i], C[i]});
adj[V[i]].pb({U[i], C[i]});
}
dist = vi(n, INF);
dist[0] = 0;
auto [u, d] = dijkstra();
send(d, CLOG);
waitDist = 1;
}
void ReceiveB(bool x) {
qu.push(x);
bool found = 0;
if (waitDist) {
if (qu.size() == CLOG) {
int nd = get(CLOG) + pd;
auto [u, d] = dijkstra();
cerr << "B " << nd << ' ' << d << '\n';
if (d <= nd) {
send(u, NLOG);
pd = d;
vis[u] = 1;
found = 1;
relax(u);
} else {
waitDist = 0;
pd = nd;
}
}
} else {
if (qu.size() == NLOG) {
int u = get(NLOG);
cerr << "B u " << u << '\n';
dist[u] = pd;
relax(u);
vis[u] = 1;
waitDist = 1;
found = 1;
}
}
if (found) {
auto [u, d] = dijkstra();
cerr << " B " << u << ' ' << d << '\n';
if (u != -1) {
send(min(d - pd, FINF), CLOG);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
10120 KB |
Output is correct |
2 |
Correct |
7 ms |
9872 KB |
Output is correct |
3 |
Correct |
517 ms |
10064 KB |
Output is correct |
4 |
Correct |
583 ms |
19396 KB |
Output is correct |
5 |
Correct |
31 ms |
10128 KB |
Output is correct |
6 |
Correct |
520 ms |
11524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9872 KB |
Output is correct |
2 |
Correct |
491 ms |
10180 KB |
Output is correct |
3 |
Correct |
477 ms |
10276 KB |
Output is correct |
4 |
Correct |
608 ms |
36944 KB |
Output is correct |
5 |
Correct |
651 ms |
33576 KB |
Output is correct |
6 |
Correct |
104 ms |
9872 KB |
Output is correct |
7 |
Correct |
623 ms |
33508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
407 ms |
10132 KB |
Output is correct |
2 |
Correct |
6 ms |
9872 KB |
Output is correct |
3 |
Correct |
439 ms |
10060 KB |
Output is correct |
4 |
Correct |
378 ms |
10152 KB |
Output is correct |
5 |
Correct |
546 ms |
10192 KB |
Output is correct |
6 |
Correct |
424 ms |
10156 KB |
Output is correct |
7 |
Correct |
426 ms |
10020 KB |
Output is correct |
8 |
Correct |
526 ms |
10076 KB |
Output is correct |
9 |
Correct |
463 ms |
10072 KB |
Output is correct |
10 |
Correct |
469 ms |
10064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
9952 KB |
Output is correct |
2 |
Correct |
208 ms |
9928 KB |
Output is correct |
3 |
Correct |
285 ms |
22488 KB |
Output is correct |
4 |
Correct |
220 ms |
9976 KB |
Output is correct |
5 |
Correct |
283 ms |
19200 KB |
Output is correct |
6 |
Correct |
205 ms |
9976 KB |
Output is correct |
7 |
Correct |
247 ms |
10132 KB |
Output is correct |
8 |
Correct |
228 ms |
10124 KB |
Output is correct |
9 |
Correct |
260 ms |
27512 KB |
Output is correct |
10 |
Correct |
349 ms |
27520 KB |
Output is correct |
11 |
Correct |
418 ms |
44972 KB |
Output is correct |
12 |
Correct |
362 ms |
40148 KB |
Output is correct |
13 |
Correct |
197 ms |
10152 KB |
Output is correct |
14 |
Correct |
7 ms |
9872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
9952 KB |
Output is correct |
2 |
Correct |
208 ms |
9928 KB |
Output is correct |
3 |
Correct |
285 ms |
22488 KB |
Output is correct |
4 |
Correct |
220 ms |
9976 KB |
Output is correct |
5 |
Correct |
283 ms |
19200 KB |
Output is correct |
6 |
Correct |
205 ms |
9976 KB |
Output is correct |
7 |
Correct |
247 ms |
10132 KB |
Output is correct |
8 |
Correct |
228 ms |
10124 KB |
Output is correct |
9 |
Correct |
260 ms |
27512 KB |
Output is correct |
10 |
Correct |
349 ms |
27520 KB |
Output is correct |
11 |
Correct |
418 ms |
44972 KB |
Output is correct |
12 |
Correct |
362 ms |
40148 KB |
Output is correct |
13 |
Correct |
197 ms |
10152 KB |
Output is correct |
14 |
Correct |
7 ms |
9872 KB |
Output is correct |
15 |
Correct |
261 ms |
9944 KB |
Output is correct |
16 |
Correct |
219 ms |
10064 KB |
Output is correct |
17 |
Correct |
269 ms |
9872 KB |
Output is correct |
18 |
Correct |
294 ms |
19436 KB |
Output is correct |
19 |
Correct |
298 ms |
9872 KB |
Output is correct |
20 |
Correct |
298 ms |
19624 KB |
Output is correct |
21 |
Correct |
260 ms |
10128 KB |
Output is correct |
22 |
Correct |
272 ms |
10128 KB |
Output is correct |
23 |
Correct |
339 ms |
31592 KB |
Output is correct |
24 |
Correct |
345 ms |
31456 KB |
Output is correct |
25 |
Correct |
516 ms |
52956 KB |
Output is correct |
26 |
Correct |
461 ms |
45792 KB |
Output is correct |
27 |
Correct |
245 ms |
10148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
9952 KB |
Output is correct |
2 |
Correct |
208 ms |
9928 KB |
Output is correct |
3 |
Correct |
285 ms |
22488 KB |
Output is correct |
4 |
Correct |
220 ms |
9976 KB |
Output is correct |
5 |
Correct |
283 ms |
19200 KB |
Output is correct |
6 |
Correct |
205 ms |
9976 KB |
Output is correct |
7 |
Correct |
247 ms |
10132 KB |
Output is correct |
8 |
Correct |
228 ms |
10124 KB |
Output is correct |
9 |
Correct |
260 ms |
27512 KB |
Output is correct |
10 |
Correct |
349 ms |
27520 KB |
Output is correct |
11 |
Correct |
418 ms |
44972 KB |
Output is correct |
12 |
Correct |
362 ms |
40148 KB |
Output is correct |
13 |
Correct |
197 ms |
10152 KB |
Output is correct |
14 |
Correct |
7 ms |
9872 KB |
Output is correct |
15 |
Correct |
261 ms |
9944 KB |
Output is correct |
16 |
Correct |
219 ms |
10064 KB |
Output is correct |
17 |
Correct |
269 ms |
9872 KB |
Output is correct |
18 |
Correct |
294 ms |
19436 KB |
Output is correct |
19 |
Correct |
298 ms |
9872 KB |
Output is correct |
20 |
Correct |
298 ms |
19624 KB |
Output is correct |
21 |
Correct |
260 ms |
10128 KB |
Output is correct |
22 |
Correct |
272 ms |
10128 KB |
Output is correct |
23 |
Correct |
339 ms |
31592 KB |
Output is correct |
24 |
Correct |
345 ms |
31456 KB |
Output is correct |
25 |
Correct |
516 ms |
52956 KB |
Output is correct |
26 |
Correct |
461 ms |
45792 KB |
Output is correct |
27 |
Correct |
245 ms |
10148 KB |
Output is correct |
28 |
Correct |
281 ms |
10076 KB |
Output is correct |
29 |
Correct |
289 ms |
10056 KB |
Output is correct |
30 |
Correct |
500 ms |
33516 KB |
Output is correct |
31 |
Correct |
298 ms |
10064 KB |
Output is correct |
32 |
Correct |
445 ms |
30484 KB |
Output is correct |
33 |
Correct |
263 ms |
10124 KB |
Output is correct |
34 |
Correct |
375 ms |
10160 KB |
Output is correct |
35 |
Correct |
368 ms |
10156 KB |
Output is correct |
36 |
Correct |
408 ms |
33964 KB |
Output is correct |
37 |
Correct |
470 ms |
34224 KB |
Output is correct |
38 |
Correct |
574 ms |
58168 KB |
Output is correct |
39 |
Correct |
603 ms |
53408 KB |
Output is correct |
40 |
Correct |
306 ms |
10128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
534 ms |
10120 KB |
Output is correct |
2 |
Correct |
7 ms |
9872 KB |
Output is correct |
3 |
Correct |
517 ms |
10064 KB |
Output is correct |
4 |
Correct |
583 ms |
19396 KB |
Output is correct |
5 |
Correct |
31 ms |
10128 KB |
Output is correct |
6 |
Correct |
520 ms |
11524 KB |
Output is correct |
7 |
Correct |
6 ms |
9872 KB |
Output is correct |
8 |
Correct |
491 ms |
10180 KB |
Output is correct |
9 |
Correct |
477 ms |
10276 KB |
Output is correct |
10 |
Correct |
608 ms |
36944 KB |
Output is correct |
11 |
Correct |
651 ms |
33576 KB |
Output is correct |
12 |
Correct |
104 ms |
9872 KB |
Output is correct |
13 |
Correct |
623 ms |
33508 KB |
Output is correct |
14 |
Correct |
407 ms |
10132 KB |
Output is correct |
15 |
Correct |
6 ms |
9872 KB |
Output is correct |
16 |
Correct |
439 ms |
10060 KB |
Output is correct |
17 |
Correct |
378 ms |
10152 KB |
Output is correct |
18 |
Correct |
546 ms |
10192 KB |
Output is correct |
19 |
Correct |
424 ms |
10156 KB |
Output is correct |
20 |
Correct |
426 ms |
10020 KB |
Output is correct |
21 |
Correct |
526 ms |
10076 KB |
Output is correct |
22 |
Correct |
463 ms |
10072 KB |
Output is correct |
23 |
Correct |
469 ms |
10064 KB |
Output is correct |
24 |
Correct |
160 ms |
9952 KB |
Output is correct |
25 |
Correct |
208 ms |
9928 KB |
Output is correct |
26 |
Correct |
285 ms |
22488 KB |
Output is correct |
27 |
Correct |
220 ms |
9976 KB |
Output is correct |
28 |
Correct |
283 ms |
19200 KB |
Output is correct |
29 |
Correct |
205 ms |
9976 KB |
Output is correct |
30 |
Correct |
247 ms |
10132 KB |
Output is correct |
31 |
Correct |
228 ms |
10124 KB |
Output is correct |
32 |
Correct |
260 ms |
27512 KB |
Output is correct |
33 |
Correct |
349 ms |
27520 KB |
Output is correct |
34 |
Correct |
418 ms |
44972 KB |
Output is correct |
35 |
Correct |
362 ms |
40148 KB |
Output is correct |
36 |
Correct |
197 ms |
10152 KB |
Output is correct |
37 |
Correct |
7 ms |
9872 KB |
Output is correct |
38 |
Correct |
261 ms |
9944 KB |
Output is correct |
39 |
Correct |
219 ms |
10064 KB |
Output is correct |
40 |
Correct |
269 ms |
9872 KB |
Output is correct |
41 |
Correct |
294 ms |
19436 KB |
Output is correct |
42 |
Correct |
298 ms |
9872 KB |
Output is correct |
43 |
Correct |
298 ms |
19624 KB |
Output is correct |
44 |
Correct |
260 ms |
10128 KB |
Output is correct |
45 |
Correct |
272 ms |
10128 KB |
Output is correct |
46 |
Correct |
339 ms |
31592 KB |
Output is correct |
47 |
Correct |
345 ms |
31456 KB |
Output is correct |
48 |
Correct |
516 ms |
52956 KB |
Output is correct |
49 |
Correct |
461 ms |
45792 KB |
Output is correct |
50 |
Correct |
245 ms |
10148 KB |
Output is correct |
51 |
Correct |
281 ms |
10076 KB |
Output is correct |
52 |
Correct |
289 ms |
10056 KB |
Output is correct |
53 |
Correct |
500 ms |
33516 KB |
Output is correct |
54 |
Correct |
298 ms |
10064 KB |
Output is correct |
55 |
Correct |
445 ms |
30484 KB |
Output is correct |
56 |
Correct |
263 ms |
10124 KB |
Output is correct |
57 |
Correct |
375 ms |
10160 KB |
Output is correct |
58 |
Correct |
368 ms |
10156 KB |
Output is correct |
59 |
Correct |
408 ms |
33964 KB |
Output is correct |
60 |
Correct |
470 ms |
34224 KB |
Output is correct |
61 |
Correct |
574 ms |
58168 KB |
Output is correct |
62 |
Correct |
603 ms |
53408 KB |
Output is correct |
63 |
Correct |
306 ms |
10128 KB |
Output is correct |
64 |
Correct |
426 ms |
10240 KB |
Output is correct |
65 |
Correct |
568 ms |
35808 KB |
Output is correct |
66 |
Correct |
600 ms |
32592 KB |
Output is correct |
67 |
Correct |
482 ms |
10296 KB |
Output is correct |
68 |
Correct |
415 ms |
10420 KB |
Output is correct |
69 |
Correct |
792 ms |
56876 KB |
Output is correct |
70 |
Correct |
754 ms |
48820 KB |
Output is correct |
71 |
Correct |
484 ms |
14308 KB |
Output is correct |
72 |
Correct |
418 ms |
10504 KB |
Output is correct |