#include "Azer.h"
#include <vector>
#include <iostream>
#include "assert.h"
using namespace std;
#define ll long long
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
const int inf = (1LL<<28) - 1;
const int wbit = 9, nbit = 11;
int N;
int done = 0;
int dis[maxn];
bool vis[maxn];
vector<pii> adj[maxn];
vector<bool> buf;
int wait = 0; //0:weight, 1:node
int cur = 0, bind = 0, bval = 0;
int uind = 0, uval = 0;
void send_weight(int w) {
assert(w >= 0);
if (w >= (1<<wbit)) w = (1<<wbit) - 1;
for (int i = 0;i < wbit;i++) {
SendA(w & (1<<i));
}
}
void send_node(int id) {
assert(id >= 0);
for (int i = 0;i < nbit;i++) {
SendA(id & (1<<i));
}
}
int getnum() {
int siz = 1;
if (wait == 0) siz = wbit;
else if (wait == 1) siz = nbit;
int ret = 0;
for (int i = 0;i < siz;i++) {
ret = ret+ (buf[i] ? 1<<i : 0);
}
buf.erase(buf.begin(), buf.begin() + siz);
return ret;
}
void get_best() {
debug("A dis");
//pary(dis, dis + N);
//pary(vis, vis + N);
int best = inf;
bind = 0;
for (int j = 0;j < N;j++) {
if (!vis[j] && dis[j] < best) {
best = dis[j];
bind = j;
}
}
wait = 0;
debug("Send weight A ", cur, best - cur);
bval = best - cur;
send_weight(best - cur);
}
void solve() {
if (wait == 0 && buf.size() >= wbit) {
uval = getnum();
if (bval <= uval) {
for (auto [v, e]:adj[bind]) {
if (dis[bind] + e < dis[v]) {
dis[v] = dis[bind] + e;
}
}
vis[bind] = 1;
cur = dis[bind];
if (++done >= N) Answer();
else {
debug("Send A node ", bind);
send_node(bind);
get_best();
}
return;
}
wait = 1;
solve();
} else if (wait == 1 && buf.size() >= nbit){
uind = getnum();
dis[uind] = uval + cur;
vis[uind] = 1;
for (auto [v, e]:adj[uind]) {
if (dis[uind] + e < dis[v]) {
dis[v] = dis[uind] + e;
}
}
cur += uval;
if (++done >= N) Answer();
else {
get_best();
}
}
}
} // namespace
std::vector<int> Answer() {
std::vector<int> ans(N);
for (int k = 0; k < N; ++k) {
ans[k] = dis[k];
}
return ans;
}
void ReceiveA(bool x) {
buf.push_back(x);
solve();
}
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) {
adj[U[i]].push_back({V[i], C[i]});
adj[V[i]].push_back({U[i], C[i]});
}
for (int i = 0;i < N;i++) dis[i] = inf, vis[i] = 0;
dis[0] = 0;
get_best();
}
#include "Baijan.h"
#include <vector>
#include <iostream>
#include "assert.h"
using namespace std;
#define ll long long
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second
namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
const int inf = (1LL<<28) - 1;
const int wbit = 9, nbit = 11;
int N;
int done = 0;
int dis[maxn];
bool vis[maxn];
vector<pii> adj[maxn];
vector<bool> buf;
int wait = 0; //0:weight, 1:node
int cur = 0, bind = 0;
int uind = 0, uval = 0;
void send_weight(int w) {
assert(w >= 0);
if (w >= (1<<wbit)) w = (1<<wbit) - 1;
for (int i = 0;i < wbit;i++) {
SendB(w & (1<<i));
}
}
void send_node(int id) {
assert(id >= 0);
for (int i = 0;i < nbit;i++) {
SendB(id & (1<<i));
}
}
int getnum() {
int siz = 1;
if (wait == 0) siz = wbit;
else if (wait == 1) siz = nbit;
int ret = 0;
for (int i = 0;i < siz;i++) {
ret = ret + (buf[i] ? 1<<i : 0);
}
buf.erase(buf.begin(), buf.begin() + siz);
return ret;
}
void get_best() {
int best = inf;
bind = 0;
for (int j = 0;j < N;j++) {
if (!vis[j] && dis[j] < best) {
best = dis[j];
bind = j;
}
}
debug("B best", bind, cur, best - cur, uval);
send_weight(best - cur);
if (best - cur < uval) {
debug("Send b wei ", cur, best - cur);
send_node(bind);
for (auto [v, e]:adj[bind]) {
if (dis[bind] + e < dis[v]) {
dis[v] = dis[bind] + e;
}
}
debug("vis b", bind);
vis[bind] = 1;
cur = dis[bind];
wait = 0;
} else {
wait = 1;
}
}
void solve() {
if (wait == 0 && buf.size() >= wbit) {
uval = getnum();
get_best();
} else if (wait == 1 && buf.size() >= nbit){
uind = getnum();
debug("read B node", uind);
dis[uind] = uval + cur;
vis[uind] = 1;
for (auto [v, e]:adj[uind]) {
if (dis[uind] + e < dis[v]) {
dis[v] = dis[uind] + e;
}
}
cur += uval;
wait = 0;
}
}
} // namespace
void ReceiveB(bool x) {
buf.push_back(x);
solve();
}
void InitB(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) {
adj[U[i]].push_back({V[i], C[i]});
adj[V[i]].push_back({U[i], C[i]});
}
for (int i = 0;i < N;i++) dis[i] = inf, vis[i] = 0;
dis[0] = 0;
}
Compilation message
Azer.cpp: In function 'void {anonymous}::get_best()':
Azer.cpp:21:20: warning: statement has no effect [-Wunused-value]
21 | #define debug(...) 0
| ^
Azer.cpp:66:2: note: in expansion of macro 'debug'
66 | debug("A dis");
| ^~~~~
Azer.cpp:21:20: warning: statement has no effect [-Wunused-value]
21 | #define debug(...) 0
| ^
Azer.cpp:78:2: note: in expansion of macro 'debug'
78 | debug("Send weight A ", cur, best - cur);
| ^~~~~
Azer.cpp: In function 'void {anonymous}::solve()':
Azer.cpp:21:20: warning: statement has no effect [-Wunused-value]
21 | #define debug(...) 0
| ^
Azer.cpp:96:5: note: in expansion of macro 'debug'
96 | debug("Send A node ", bind);
| ^~~~~
Baijan.cpp: In function 'void {anonymous}::get_best()':
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) 0
| ^
Baijan.cpp:75:2: note: in expansion of macro 'debug'
75 | debug("B best", bind, cur, best - cur, uval);
| ^~~~~
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) 0
| ^
Baijan.cpp:78:3: note: in expansion of macro 'debug'
78 | debug("Send b wei ", cur, best - cur);
| ^~~~~
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) 0
| ^
Baijan.cpp:85:3: note: in expansion of macro 'debug'
85 | debug("vis b", bind);
| ^~~~~
Baijan.cpp: In function 'void {anonymous}::solve()':
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) 0
| ^
Baijan.cpp:100:3: note: in expansion of macro 'debug'
100 | debug("read B node", uind);
| ^~~~~
Baijan.cpp: At global scope:
Baijan.cpp:28:5: warning: '{anonymous}::done' defined but not used [-Wunused-variable]
28 | int done = 0;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
505 ms |
780 KB |
Output is correct |
2 |
Correct |
2 ms |
648 KB |
Output is correct |
3 |
Correct |
485 ms |
780 KB |
Output is correct |
4 |
Correct |
643 ms |
10244 KB |
Output is correct |
5 |
Correct |
30 ms |
912 KB |
Output is correct |
6 |
Correct |
571 ms |
2196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
648 KB |
Output is correct |
2 |
Correct |
468 ms |
736 KB |
Output is correct |
3 |
Correct |
524 ms |
896 KB |
Output is correct |
4 |
Correct |
713 ms |
27528 KB |
Output is correct |
5 |
Correct |
589 ms |
24068 KB |
Output is correct |
6 |
Correct |
111 ms |
648 KB |
Output is correct |
7 |
Correct |
660 ms |
24324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
600 ms |
716 KB |
Output is correct |
2 |
Correct |
2 ms |
648 KB |
Output is correct |
3 |
Correct |
479 ms |
660 KB |
Output is correct |
4 |
Correct |
498 ms |
736 KB |
Output is correct |
5 |
Correct |
445 ms |
736 KB |
Output is correct |
6 |
Correct |
503 ms |
720 KB |
Output is correct |
7 |
Correct |
503 ms |
732 KB |
Output is correct |
8 |
Correct |
470 ms |
660 KB |
Output is correct |
9 |
Correct |
589 ms |
780 KB |
Output is correct |
10 |
Correct |
403 ms |
780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
648 KB |
Output is correct |
2 |
Correct |
225 ms |
768 KB |
Output is correct |
3 |
Correct |
321 ms |
13192 KB |
Output is correct |
4 |
Correct |
267 ms |
648 KB |
Output is correct |
5 |
Correct |
279 ms |
10124 KB |
Output is correct |
6 |
Correct |
177 ms |
684 KB |
Output is correct |
7 |
Correct |
276 ms |
648 KB |
Output is correct |
8 |
Correct |
232 ms |
648 KB |
Output is correct |
9 |
Correct |
362 ms |
18048 KB |
Output is correct |
10 |
Correct |
354 ms |
18316 KB |
Output is correct |
11 |
Correct |
436 ms |
35644 KB |
Output is correct |
12 |
Correct |
400 ms |
30596 KB |
Output is correct |
13 |
Correct |
189 ms |
648 KB |
Output is correct |
14 |
Correct |
1 ms |
648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
648 KB |
Output is correct |
2 |
Correct |
225 ms |
768 KB |
Output is correct |
3 |
Correct |
321 ms |
13192 KB |
Output is correct |
4 |
Correct |
267 ms |
648 KB |
Output is correct |
5 |
Correct |
279 ms |
10124 KB |
Output is correct |
6 |
Correct |
177 ms |
684 KB |
Output is correct |
7 |
Correct |
276 ms |
648 KB |
Output is correct |
8 |
Correct |
232 ms |
648 KB |
Output is correct |
9 |
Correct |
362 ms |
18048 KB |
Output is correct |
10 |
Correct |
354 ms |
18316 KB |
Output is correct |
11 |
Correct |
436 ms |
35644 KB |
Output is correct |
12 |
Correct |
400 ms |
30596 KB |
Output is correct |
13 |
Correct |
189 ms |
648 KB |
Output is correct |
14 |
Correct |
1 ms |
648 KB |
Output is correct |
15 |
Correct |
284 ms |
648 KB |
Output is correct |
16 |
Correct |
318 ms |
712 KB |
Output is correct |
17 |
Correct |
319 ms |
648 KB |
Output is correct |
18 |
Correct |
275 ms |
10008 KB |
Output is correct |
19 |
Correct |
270 ms |
712 KB |
Output is correct |
20 |
Correct |
375 ms |
10356 KB |
Output is correct |
21 |
Correct |
284 ms |
648 KB |
Output is correct |
22 |
Correct |
311 ms |
736 KB |
Output is correct |
23 |
Correct |
444 ms |
22140 KB |
Output is correct |
24 |
Correct |
442 ms |
22148 KB |
Output is correct |
25 |
Correct |
496 ms |
43504 KB |
Output is correct |
26 |
Correct |
371 ms |
36348 KB |
Output is correct |
27 |
Correct |
260 ms |
752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
648 KB |
Output is correct |
2 |
Correct |
225 ms |
768 KB |
Output is correct |
3 |
Correct |
321 ms |
13192 KB |
Output is correct |
4 |
Correct |
267 ms |
648 KB |
Output is correct |
5 |
Correct |
279 ms |
10124 KB |
Output is correct |
6 |
Correct |
177 ms |
684 KB |
Output is correct |
7 |
Correct |
276 ms |
648 KB |
Output is correct |
8 |
Correct |
232 ms |
648 KB |
Output is correct |
9 |
Correct |
362 ms |
18048 KB |
Output is correct |
10 |
Correct |
354 ms |
18316 KB |
Output is correct |
11 |
Correct |
436 ms |
35644 KB |
Output is correct |
12 |
Correct |
400 ms |
30596 KB |
Output is correct |
13 |
Correct |
189 ms |
648 KB |
Output is correct |
14 |
Correct |
1 ms |
648 KB |
Output is correct |
15 |
Correct |
284 ms |
648 KB |
Output is correct |
16 |
Correct |
318 ms |
712 KB |
Output is correct |
17 |
Correct |
319 ms |
648 KB |
Output is correct |
18 |
Correct |
275 ms |
10008 KB |
Output is correct |
19 |
Correct |
270 ms |
712 KB |
Output is correct |
20 |
Correct |
375 ms |
10356 KB |
Output is correct |
21 |
Correct |
284 ms |
648 KB |
Output is correct |
22 |
Correct |
311 ms |
736 KB |
Output is correct |
23 |
Correct |
444 ms |
22140 KB |
Output is correct |
24 |
Correct |
442 ms |
22148 KB |
Output is correct |
25 |
Correct |
496 ms |
43504 KB |
Output is correct |
26 |
Correct |
371 ms |
36348 KB |
Output is correct |
27 |
Correct |
260 ms |
752 KB |
Output is correct |
28 |
Correct |
323 ms |
648 KB |
Output is correct |
29 |
Correct |
231 ms |
648 KB |
Output is correct |
30 |
Correct |
427 ms |
24196 KB |
Output is correct |
31 |
Correct |
364 ms |
652 KB |
Output is correct |
32 |
Correct |
429 ms |
21216 KB |
Output is correct |
33 |
Correct |
395 ms |
732 KB |
Output is correct |
34 |
Correct |
364 ms |
748 KB |
Output is correct |
35 |
Correct |
300 ms |
776 KB |
Output is correct |
36 |
Correct |
490 ms |
24696 KB |
Output is correct |
37 |
Correct |
518 ms |
24724 KB |
Output is correct |
38 |
Correct |
667 ms |
48876 KB |
Output is correct |
39 |
Correct |
621 ms |
44256 KB |
Output is correct |
40 |
Correct |
427 ms |
904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
505 ms |
780 KB |
Output is correct |
2 |
Correct |
2 ms |
648 KB |
Output is correct |
3 |
Correct |
485 ms |
780 KB |
Output is correct |
4 |
Correct |
643 ms |
10244 KB |
Output is correct |
5 |
Correct |
30 ms |
912 KB |
Output is correct |
6 |
Correct |
571 ms |
2196 KB |
Output is correct |
7 |
Correct |
1 ms |
648 KB |
Output is correct |
8 |
Correct |
468 ms |
736 KB |
Output is correct |
9 |
Correct |
524 ms |
896 KB |
Output is correct |
10 |
Correct |
713 ms |
27528 KB |
Output is correct |
11 |
Correct |
589 ms |
24068 KB |
Output is correct |
12 |
Correct |
111 ms |
648 KB |
Output is correct |
13 |
Correct |
660 ms |
24324 KB |
Output is correct |
14 |
Correct |
600 ms |
716 KB |
Output is correct |
15 |
Correct |
2 ms |
648 KB |
Output is correct |
16 |
Correct |
479 ms |
660 KB |
Output is correct |
17 |
Correct |
498 ms |
736 KB |
Output is correct |
18 |
Correct |
445 ms |
736 KB |
Output is correct |
19 |
Correct |
503 ms |
720 KB |
Output is correct |
20 |
Correct |
503 ms |
732 KB |
Output is correct |
21 |
Correct |
470 ms |
660 KB |
Output is correct |
22 |
Correct |
589 ms |
780 KB |
Output is correct |
23 |
Correct |
403 ms |
780 KB |
Output is correct |
24 |
Correct |
194 ms |
648 KB |
Output is correct |
25 |
Correct |
225 ms |
768 KB |
Output is correct |
26 |
Correct |
321 ms |
13192 KB |
Output is correct |
27 |
Correct |
267 ms |
648 KB |
Output is correct |
28 |
Correct |
279 ms |
10124 KB |
Output is correct |
29 |
Correct |
177 ms |
684 KB |
Output is correct |
30 |
Correct |
276 ms |
648 KB |
Output is correct |
31 |
Correct |
232 ms |
648 KB |
Output is correct |
32 |
Correct |
362 ms |
18048 KB |
Output is correct |
33 |
Correct |
354 ms |
18316 KB |
Output is correct |
34 |
Correct |
436 ms |
35644 KB |
Output is correct |
35 |
Correct |
400 ms |
30596 KB |
Output is correct |
36 |
Correct |
189 ms |
648 KB |
Output is correct |
37 |
Correct |
1 ms |
648 KB |
Output is correct |
38 |
Correct |
284 ms |
648 KB |
Output is correct |
39 |
Correct |
318 ms |
712 KB |
Output is correct |
40 |
Correct |
319 ms |
648 KB |
Output is correct |
41 |
Correct |
275 ms |
10008 KB |
Output is correct |
42 |
Correct |
270 ms |
712 KB |
Output is correct |
43 |
Correct |
375 ms |
10356 KB |
Output is correct |
44 |
Correct |
284 ms |
648 KB |
Output is correct |
45 |
Correct |
311 ms |
736 KB |
Output is correct |
46 |
Correct |
444 ms |
22140 KB |
Output is correct |
47 |
Correct |
442 ms |
22148 KB |
Output is correct |
48 |
Correct |
496 ms |
43504 KB |
Output is correct |
49 |
Correct |
371 ms |
36348 KB |
Output is correct |
50 |
Correct |
260 ms |
752 KB |
Output is correct |
51 |
Correct |
323 ms |
648 KB |
Output is correct |
52 |
Correct |
231 ms |
648 KB |
Output is correct |
53 |
Correct |
427 ms |
24196 KB |
Output is correct |
54 |
Correct |
364 ms |
652 KB |
Output is correct |
55 |
Correct |
429 ms |
21216 KB |
Output is correct |
56 |
Correct |
395 ms |
732 KB |
Output is correct |
57 |
Correct |
364 ms |
748 KB |
Output is correct |
58 |
Correct |
300 ms |
776 KB |
Output is correct |
59 |
Correct |
490 ms |
24696 KB |
Output is correct |
60 |
Correct |
518 ms |
24724 KB |
Output is correct |
61 |
Correct |
667 ms |
48876 KB |
Output is correct |
62 |
Correct |
621 ms |
44256 KB |
Output is correct |
63 |
Correct |
427 ms |
904 KB |
Output is correct |
64 |
Correct |
536 ms |
944 KB |
Output is correct |
65 |
Correct |
671 ms |
26488 KB |
Output is correct |
66 |
Correct |
657 ms |
23408 KB |
Output is correct |
67 |
Correct |
424 ms |
932 KB |
Output is correct |
68 |
Correct |
514 ms |
936 KB |
Output is correct |
69 |
Correct |
782 ms |
47604 KB |
Output is correct |
70 |
Correct |
645 ms |
39524 KB |
Output is correct |
71 |
Correct |
449 ms |
4976 KB |
Output is correct |
72 |
Correct |
558 ms |
1160 KB |
Output is correct |