#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace Azer{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
const int N=2010;
int f[N], n, vis[N];
vector<pair<int, int>> g[N];
int buffer;
int buffer_size;
int waiting_size;
int last_value;
int remain;
int ceil_log2(){
return 32-__builtin_clz(remain);
}
int find_idx(int u){
int ans=0;
for (int i=0; i<u; ++i) ans+=!vis[i];
return ans;
}
int find_node(int idx){
int ans=0;
while (idx>=(!vis[ans])) idx-=!vis[ans], ++ans;
return ans;
}
void FakeSendA(int size, int data){
for (int i=size-1; i>=0; --i) SendA(data>>i&1);
}
void adjust_pq(){
while (pq.size() && vis[pq.top().second]) pq.pop();
}
void reset_buffer(){
buffer=0;
buffer_size=0;
}
void optimize(int _u=-1, int _f=-1){
--remain;
int u=-1;
if (_u==-1){
last_value=pq.top().first;
u=pq.top().second; pq.pop();
}else{
last_value=_f;
u=_u; f[u]=_f;
}
vis[u]=1;
for (auto &e:g[u]){
int v=e.first, w=e.second;
if (f[v]>f[u]+w) pq.emplace(f[v]=f[u]+w, v);
}
adjust_pq();
}
}
void InitA(int N, int A, vector<int> U, vector<int> V,
vector<int> C) {
Azer::n=N;
Azer::remain=N;
for (int i=0; i<A; ++i) Azer::g[U[i]].emplace_back(V[i], C[i]), Azer::g[V[i]].emplace_back(U[i], C[i]);
Azer::pq.emplace(Azer::f[0]=0, 0);
for (int i=1; i<N; ++i) Azer::pq.emplace(Azer::f[i]=(1<<20)-1, i);
if (Azer::pq.size()){
Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first));
Azer::waiting_size=1;
}
}
void ReceiveA(bool x) {
++Azer::buffer_size;
Azer::buffer<<=1; Azer::buffer|=x;
if (Azer::buffer_size==Azer::waiting_size){
if (Azer::waiting_size==1){
if (Azer::buffer==0){
Azer::FakeSendA(Azer::ceil_log2(), Azer::find_idx(Azer::pq.top().second));
Azer::optimize();
if (Azer::pq.size()){
Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first-Azer::last_value));
Azer::waiting_size=1;
}
}else{
Azer::waiting_size=9+Azer::ceil_log2();
}
}else{
int v=Azer::find_node(Azer::buffer&((1<<Azer::ceil_log2())-1)), f=(Azer::buffer>>Azer::ceil_log2())+Azer::last_value;
Azer::optimize(v, f);
if (Azer::pq.size()){
Azer::FakeSendA(9, (Azer::pq.top().first==((1<<20)-1)?511:Azer::pq.top().first-Azer::last_value));
Azer::waiting_size=1;
}
}
Azer::reset_buffer();
}
}
vector<int> Answer() {
return vector<int>(Azer::f, Azer::f+Azer::n);
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace Baijan{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
const int N=2010;
int f[N], n, vis[N];
vector<pair<int, int>> g[N];
int buffer;
int buffer_size;
int waiting_size;
int last_value;
int remain;
int ceil_log2(){
return 32-__builtin_clz(remain);
}
int find_idx(int u){
int ans=0;
for (int i=0; i<u; ++i) ans+=!vis[i];
return ans;
}
int find_node(int idx){
int ans=0;
while (idx>=(!vis[ans])) idx-=!vis[ans], ++ans;
return ans;
}
void FakeSendB(int size, int data){
for (int i=size-1; i>=0; --i) SendB(data>>i&1);
}
void adjust_pq(){
while (pq.size() && vis[pq.top().second]) pq.pop();
}
void reset_buffer(){
buffer=0;
buffer_size=0;
}
void optimize(int _u=-1, int _f=-1){
--remain;
int u=-1;
if (_u==-1){
last_value=pq.top().first;
u=pq.top().second; pq.pop();
}else{
last_value=_f;
u=_u; f[u]=_f;
}
vis[u]=1;
for (auto &e:g[u]){
int v=e.first, w=e.second;
if (f[v]>f[u]+w) pq.emplace(f[v]=f[u]+w, v);
}
adjust_pq();
}
}
void InitB(int N, int B, vector<int> S, vector<int> T,
vector<int> D) {
Baijan::n=N;
Baijan::remain=N;
memset(Baijan::f, 0x3f, sizeof Baijan::f);
for (int i=0; i<B; ++i) Baijan::g[S[i]].emplace_back(T[i], D[i]), Baijan::g[T[i]].emplace_back(S[i], D[i]);
Baijan::pq.emplace(Baijan::f[0]=0, 0);
for (int i=1; i<N; ++i) Baijan::pq.emplace(Baijan::f[i]=(1<<20)-1, i);
Baijan::waiting_size=9;
}
void ReceiveB(bool y) {
++Baijan::buffer_size;
Baijan::buffer<<=1; Baijan::buffer|=y;
if (Baijan::buffer_size==Baijan::waiting_size){
if (Baijan::waiting_size==9){
int fa=Baijan::buffer+Baijan::last_value;
if (fa<=Baijan::pq.top().first){
Baijan::FakeSendB(1, 0);
Baijan::waiting_size+=Baijan::ceil_log2();
if (Baijan::ceil_log2()==0){
int v=Baijan::find_node(Baijan::buffer&((1<<Baijan::ceil_log2())-1)), f=(Baijan::buffer>>Baijan::ceil_log2())+Baijan::last_value;
Baijan::optimize(v, f);
Baijan::waiting_size=9;
Baijan::reset_buffer();
}
}else{
Baijan::FakeSendB(1, 1);
Baijan::FakeSendB(9+Baijan::ceil_log2(), (Baijan::pq.top().first==((1<<20)-1)?511:Baijan::pq.top().first-Baijan::last_value)<<Baijan::ceil_log2()|Baijan::find_idx(Baijan::pq.top().second));
if (Baijan::pq.size()) Baijan::optimize();
Baijan::waiting_size=9;
Baijan::reset_buffer();
}
}else{
int v=Baijan::find_node(Baijan::buffer&((1<<Baijan::ceil_log2())-1)), f=(Baijan::buffer>>Baijan::ceil_log2())+Baijan::last_value;
Baijan::optimize(v, f);
Baijan::waiting_size=9;
Baijan::reset_buffer();
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
289 ms |
1160 KB |
Output is correct |
2 |
Correct |
0 ms |
916 KB |
Output is correct |
3 |
Correct |
381 ms |
1164 KB |
Output is correct |
4 |
Correct |
332 ms |
10400 KB |
Output is correct |
5 |
Correct |
11 ms |
920 KB |
Output is correct |
6 |
Correct |
349 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
664 KB |
Output is correct |
2 |
Correct |
265 ms |
1200 KB |
Output is correct |
3 |
Correct |
211 ms |
1244 KB |
Output is correct |
4 |
Correct |
388 ms |
28024 KB |
Output is correct |
5 |
Correct |
307 ms |
24472 KB |
Output is correct |
6 |
Correct |
63 ms |
664 KB |
Output is correct |
7 |
Correct |
371 ms |
24816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
267 ms |
1168 KB |
Output is correct |
2 |
Correct |
1 ms |
664 KB |
Output is correct |
3 |
Correct |
288 ms |
1140 KB |
Output is correct |
4 |
Correct |
234 ms |
1200 KB |
Output is correct |
5 |
Correct |
273 ms |
1444 KB |
Output is correct |
6 |
Correct |
253 ms |
1432 KB |
Output is correct |
7 |
Correct |
251 ms |
1188 KB |
Output is correct |
8 |
Correct |
274 ms |
1144 KB |
Output is correct |
9 |
Correct |
291 ms |
1140 KB |
Output is correct |
10 |
Correct |
293 ms |
1172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
856 KB |
Output is correct |
2 |
Correct |
152 ms |
1036 KB |
Output is correct |
3 |
Correct |
137 ms |
13588 KB |
Output is correct |
4 |
Correct |
132 ms |
1136 KB |
Output is correct |
5 |
Correct |
167 ms |
10096 KB |
Output is correct |
6 |
Correct |
95 ms |
1072 KB |
Output is correct |
7 |
Correct |
119 ms |
1404 KB |
Output is correct |
8 |
Correct |
134 ms |
1112 KB |
Output is correct |
9 |
Correct |
184 ms |
18328 KB |
Output is correct |
10 |
Correct |
213 ms |
18608 KB |
Output is correct |
11 |
Correct |
349 ms |
35860 KB |
Output is correct |
12 |
Correct |
239 ms |
30764 KB |
Output is correct |
13 |
Correct |
145 ms |
1172 KB |
Output is correct |
14 |
Correct |
0 ms |
664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
856 KB |
Output is correct |
2 |
Correct |
152 ms |
1036 KB |
Output is correct |
3 |
Correct |
137 ms |
13588 KB |
Output is correct |
4 |
Correct |
132 ms |
1136 KB |
Output is correct |
5 |
Correct |
167 ms |
10096 KB |
Output is correct |
6 |
Correct |
95 ms |
1072 KB |
Output is correct |
7 |
Correct |
119 ms |
1404 KB |
Output is correct |
8 |
Correct |
134 ms |
1112 KB |
Output is correct |
9 |
Correct |
184 ms |
18328 KB |
Output is correct |
10 |
Correct |
213 ms |
18608 KB |
Output is correct |
11 |
Correct |
349 ms |
35860 KB |
Output is correct |
12 |
Correct |
239 ms |
30764 KB |
Output is correct |
13 |
Correct |
145 ms |
1172 KB |
Output is correct |
14 |
Correct |
0 ms |
664 KB |
Output is correct |
15 |
Correct |
151 ms |
1144 KB |
Output is correct |
16 |
Correct |
103 ms |
1164 KB |
Output is correct |
17 |
Correct |
115 ms |
1164 KB |
Output is correct |
18 |
Correct |
160 ms |
10564 KB |
Output is correct |
19 |
Correct |
146 ms |
1164 KB |
Output is correct |
20 |
Correct |
184 ms |
10556 KB |
Output is correct |
21 |
Correct |
121 ms |
1180 KB |
Output is correct |
22 |
Correct |
150 ms |
1184 KB |
Output is correct |
23 |
Correct |
252 ms |
22440 KB |
Output is correct |
24 |
Correct |
279 ms |
22592 KB |
Output is correct |
25 |
Correct |
316 ms |
43668 KB |
Output is correct |
26 |
Correct |
271 ms |
36548 KB |
Output is correct |
27 |
Correct |
123 ms |
1480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
856 KB |
Output is correct |
2 |
Correct |
152 ms |
1036 KB |
Output is correct |
3 |
Correct |
137 ms |
13588 KB |
Output is correct |
4 |
Correct |
132 ms |
1136 KB |
Output is correct |
5 |
Correct |
167 ms |
10096 KB |
Output is correct |
6 |
Correct |
95 ms |
1072 KB |
Output is correct |
7 |
Correct |
119 ms |
1404 KB |
Output is correct |
8 |
Correct |
134 ms |
1112 KB |
Output is correct |
9 |
Correct |
184 ms |
18328 KB |
Output is correct |
10 |
Correct |
213 ms |
18608 KB |
Output is correct |
11 |
Correct |
349 ms |
35860 KB |
Output is correct |
12 |
Correct |
239 ms |
30764 KB |
Output is correct |
13 |
Correct |
145 ms |
1172 KB |
Output is correct |
14 |
Correct |
0 ms |
664 KB |
Output is correct |
15 |
Correct |
151 ms |
1144 KB |
Output is correct |
16 |
Correct |
103 ms |
1164 KB |
Output is correct |
17 |
Correct |
115 ms |
1164 KB |
Output is correct |
18 |
Correct |
160 ms |
10564 KB |
Output is correct |
19 |
Correct |
146 ms |
1164 KB |
Output is correct |
20 |
Correct |
184 ms |
10556 KB |
Output is correct |
21 |
Correct |
121 ms |
1180 KB |
Output is correct |
22 |
Correct |
150 ms |
1184 KB |
Output is correct |
23 |
Correct |
252 ms |
22440 KB |
Output is correct |
24 |
Correct |
279 ms |
22592 KB |
Output is correct |
25 |
Correct |
316 ms |
43668 KB |
Output is correct |
26 |
Correct |
271 ms |
36548 KB |
Output is correct |
27 |
Correct |
123 ms |
1480 KB |
Output is correct |
28 |
Correct |
250 ms |
1152 KB |
Output is correct |
29 |
Correct |
196 ms |
1104 KB |
Output is correct |
30 |
Correct |
236 ms |
24232 KB |
Output is correct |
31 |
Correct |
236 ms |
1104 KB |
Output is correct |
32 |
Correct |
274 ms |
21444 KB |
Output is correct |
33 |
Correct |
192 ms |
1180 KB |
Output is correct |
34 |
Correct |
190 ms |
1240 KB |
Output is correct |
35 |
Correct |
256 ms |
1232 KB |
Output is correct |
36 |
Correct |
263 ms |
25020 KB |
Output is correct |
37 |
Correct |
316 ms |
25280 KB |
Output is correct |
38 |
Correct |
442 ms |
49040 KB |
Output is correct |
39 |
Correct |
350 ms |
44376 KB |
Output is correct |
40 |
Correct |
148 ms |
1768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
289 ms |
1160 KB |
Output is correct |
2 |
Correct |
0 ms |
916 KB |
Output is correct |
3 |
Correct |
381 ms |
1164 KB |
Output is correct |
4 |
Correct |
332 ms |
10400 KB |
Output is correct |
5 |
Correct |
11 ms |
920 KB |
Output is correct |
6 |
Correct |
349 ms |
2636 KB |
Output is correct |
7 |
Correct |
0 ms |
664 KB |
Output is correct |
8 |
Correct |
265 ms |
1200 KB |
Output is correct |
9 |
Correct |
211 ms |
1244 KB |
Output is correct |
10 |
Correct |
388 ms |
28024 KB |
Output is correct |
11 |
Correct |
307 ms |
24472 KB |
Output is correct |
12 |
Correct |
63 ms |
664 KB |
Output is correct |
13 |
Correct |
371 ms |
24816 KB |
Output is correct |
14 |
Correct |
267 ms |
1168 KB |
Output is correct |
15 |
Correct |
1 ms |
664 KB |
Output is correct |
16 |
Correct |
288 ms |
1140 KB |
Output is correct |
17 |
Correct |
234 ms |
1200 KB |
Output is correct |
18 |
Correct |
273 ms |
1444 KB |
Output is correct |
19 |
Correct |
253 ms |
1432 KB |
Output is correct |
20 |
Correct |
251 ms |
1188 KB |
Output is correct |
21 |
Correct |
274 ms |
1144 KB |
Output is correct |
22 |
Correct |
291 ms |
1140 KB |
Output is correct |
23 |
Correct |
293 ms |
1172 KB |
Output is correct |
24 |
Correct |
114 ms |
856 KB |
Output is correct |
25 |
Correct |
152 ms |
1036 KB |
Output is correct |
26 |
Correct |
137 ms |
13588 KB |
Output is correct |
27 |
Correct |
132 ms |
1136 KB |
Output is correct |
28 |
Correct |
167 ms |
10096 KB |
Output is correct |
29 |
Correct |
95 ms |
1072 KB |
Output is correct |
30 |
Correct |
119 ms |
1404 KB |
Output is correct |
31 |
Correct |
134 ms |
1112 KB |
Output is correct |
32 |
Correct |
184 ms |
18328 KB |
Output is correct |
33 |
Correct |
213 ms |
18608 KB |
Output is correct |
34 |
Correct |
349 ms |
35860 KB |
Output is correct |
35 |
Correct |
239 ms |
30764 KB |
Output is correct |
36 |
Correct |
145 ms |
1172 KB |
Output is correct |
37 |
Correct |
0 ms |
664 KB |
Output is correct |
38 |
Correct |
151 ms |
1144 KB |
Output is correct |
39 |
Correct |
103 ms |
1164 KB |
Output is correct |
40 |
Correct |
115 ms |
1164 KB |
Output is correct |
41 |
Correct |
160 ms |
10564 KB |
Output is correct |
42 |
Correct |
146 ms |
1164 KB |
Output is correct |
43 |
Correct |
184 ms |
10556 KB |
Output is correct |
44 |
Correct |
121 ms |
1180 KB |
Output is correct |
45 |
Correct |
150 ms |
1184 KB |
Output is correct |
46 |
Correct |
252 ms |
22440 KB |
Output is correct |
47 |
Correct |
279 ms |
22592 KB |
Output is correct |
48 |
Correct |
316 ms |
43668 KB |
Output is correct |
49 |
Correct |
271 ms |
36548 KB |
Output is correct |
50 |
Correct |
123 ms |
1480 KB |
Output is correct |
51 |
Correct |
250 ms |
1152 KB |
Output is correct |
52 |
Correct |
196 ms |
1104 KB |
Output is correct |
53 |
Correct |
236 ms |
24232 KB |
Output is correct |
54 |
Correct |
236 ms |
1104 KB |
Output is correct |
55 |
Correct |
274 ms |
21444 KB |
Output is correct |
56 |
Correct |
192 ms |
1180 KB |
Output is correct |
57 |
Correct |
190 ms |
1240 KB |
Output is correct |
58 |
Correct |
256 ms |
1232 KB |
Output is correct |
59 |
Correct |
263 ms |
25020 KB |
Output is correct |
60 |
Correct |
316 ms |
25280 KB |
Output is correct |
61 |
Correct |
442 ms |
49040 KB |
Output is correct |
62 |
Correct |
350 ms |
44376 KB |
Output is correct |
63 |
Correct |
148 ms |
1768 KB |
Output is correct |
64 |
Correct |
242 ms |
1528 KB |
Output is correct |
65 |
Correct |
352 ms |
26792 KB |
Output is correct |
66 |
Correct |
391 ms |
23496 KB |
Output is correct |
67 |
Correct |
329 ms |
1504 KB |
Output is correct |
68 |
Correct |
290 ms |
1508 KB |
Output is correct |
69 |
Correct |
622 ms |
48008 KB |
Output is correct |
70 |
Correct |
479 ms |
39740 KB |
Output is correct |
71 |
Correct |
254 ms |
5700 KB |
Output is correct |
72 |
Correct |
276 ms |
1624 KB |
Output is correct |