#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define de(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
namespace{
const int maxn=2009,inf=1e9;
int n,ls=0,t=0,fin=0,r,tmp,d[maxn];
bitset<maxn>c;
vector<pii>g[maxn];
priority_queue<pii,vector<pii>,greater<pii>>pq;
void send(int x,int l){RREP(i,l,0)SendA((x>>i)&1);}
void rlx(int u,int x){
d[u]=x;
c[u]=1;
++fin;
ls=d[u];
REP(i,0,g[u].size()){
pii&ee=g[u][i];
if(d[u]+ee.s<d[ee.f]){
d[ee.f]=d[u]+ee.s;
pq.push({d[ee.f],ee.f});
}
}
}
void proc(){
if(t==0||t==21){
while(pq.size()&&c[pq.top().s])pq.pop();
send(pq.size()?pq.top().f-ls:511,9);
t=1;
}else if(t==9){
r+=ls;
if(pq.empty()||r<pq.top().f)tmp=r;
else{
pii tt=pq.top();pq.pop();
send(tt.s,11);
t+=11;
rlx(tt.s,tt.f);
}
}else rlx(r,tmp);
}
}
void InitA(int _n,int a,vector<int>u,vector<int>v,vector<int>c) {
n=_n;
REP(i,0,a)g[u[i]].pb({v[i],c[i]}),g[v[i]].pb({u[i],c[i]});
fill(d+1,d+n,inf);
pq.push({d[0],0});
proc();
}
void ReceiveA(bool x){
if(t==1||t==10)r=0;
(r<<=1)|=x;
if(t==9||t==20)proc();
++t;
if(t==21&&fin<n)proc();
}
vector<int>Answer(){
vector<int>ret;
REP(i,0,n)ret.pb(d[i]);
return ret;
}
#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define de(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
namespace{
const int maxn=2009,inf=1e9;
int n,ls=0,t=0,fin=0,r,tmp,d[maxn];
bitset<maxn>c;
vector<pii>g[maxn];
priority_queue<pii,vector<pii>,greater<pii>>pq;
void send(int x,int l){RREP(i,l,0)SendB((x>>i)&1);}
void rlx(int u,int x){
d[u]=x;
c[u]=1;
++fin;
ls=d[u];
REP(i,0,g[u].size()){
pii&ee=g[u][i];
if(d[u]+ee.s<d[ee.f]){
d[ee.f]=d[u]+ee.s;
pq.push({d[ee.f],ee.f});
}
}
}
void proc(){
if(t==0||t==21){
while(pq.size()&&c[pq.top().s])pq.pop();
send(pq.size()?pq.top().f-ls:511,9);
t=1;
}else if(t==9){
r+=ls;
if(pq.empty()||r<=pq.top().f)tmp=r;
else{
pii tt=pq.top();pq.pop();
send(tt.s,11);
t+=11;
rlx(tt.s,tt.f);
}
}else rlx(r,tmp);
}
}
void InitB(int _n,int a,vector<int>u,vector<int>v,vector<int>c) {
n=_n;
REP(i,0,a)g[u[i]].pb({v[i],c[i]}),g[v[i]].pb({u[i],c[i]});
fill(d+1,d+n,inf);
pq.push({d[0],0});
proc();
}
void ReceiveB(bool x){
if(t==1||t==10)r=0;
(r<<=1)|=x;
if(t==9||t==20)proc();
++t;
if(t==21&&fin<n)proc();
}
Compilation message
Azer.cpp: In function 'void {anonymous}::rlx(int, int)':
Azer.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(int i=(j);i<(k);++i)
^
Azer.cpp:27:3: note: in expansion of macro 'REP'
REP(i,0,g[u].size()){
^~~
Baijan.cpp: In function 'void {anonymous}::rlx(int, int)':
Baijan.cpp:5:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(i,j,k) for(int i=(j);i<(k);++i)
^
Baijan.cpp:27:3: note: in expansion of macro 'REP'
REP(i,0,g[u].size()){
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
944 ms |
1440 KB |
Output is correct |
2 |
Correct |
8 ms |
1368 KB |
Output is correct |
3 |
Correct |
860 ms |
1520 KB |
Output is correct |
4 |
Correct |
1328 ms |
20312 KB |
Output is correct |
5 |
Correct |
74 ms |
1608 KB |
Output is correct |
6 |
Correct |
942 ms |
4128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1104 KB |
Output is correct |
2 |
Correct |
1026 ms |
1760 KB |
Output is correct |
3 |
Correct |
968 ms |
1760 KB |
Output is correct |
4 |
Correct |
1693 ms |
55088 KB |
Output is correct |
5 |
Correct |
1538 ms |
48000 KB |
Output is correct |
6 |
Correct |
316 ms |
1248 KB |
Output is correct |
7 |
Correct |
1322 ms |
48384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1054 ms |
1384 KB |
Output is correct |
2 |
Correct |
8 ms |
1256 KB |
Output is correct |
3 |
Correct |
1110 ms |
1448 KB |
Output is correct |
4 |
Correct |
966 ms |
1760 KB |
Output is correct |
5 |
Correct |
952 ms |
1832 KB |
Output is correct |
6 |
Correct |
1238 ms |
1544 KB |
Output is correct |
7 |
Correct |
1052 ms |
1504 KB |
Output is correct |
8 |
Correct |
934 ms |
1432 KB |
Output is correct |
9 |
Correct |
1150 ms |
1272 KB |
Output is correct |
10 |
Correct |
1130 ms |
1520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
1400 KB |
Output is correct |
2 |
Correct |
548 ms |
1504 KB |
Output is correct |
3 |
Correct |
708 ms |
23448 KB |
Output is correct |
4 |
Correct |
552 ms |
1600 KB |
Output is correct |
5 |
Correct |
776 ms |
17416 KB |
Output is correct |
6 |
Correct |
544 ms |
1504 KB |
Output is correct |
7 |
Correct |
346 ms |
1456 KB |
Output is correct |
8 |
Correct |
536 ms |
1760 KB |
Output is correct |
9 |
Correct |
690 ms |
36096 KB |
Output is correct |
10 |
Correct |
714 ms |
36056 KB |
Output is correct |
11 |
Correct |
1162 ms |
61136 KB |
Output is correct |
12 |
Correct |
1006 ms |
53448 KB |
Output is correct |
13 |
Correct |
366 ms |
1344 KB |
Output is correct |
14 |
Correct |
8 ms |
1248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
1400 KB |
Output is correct |
2 |
Correct |
548 ms |
1504 KB |
Output is correct |
3 |
Correct |
708 ms |
23448 KB |
Output is correct |
4 |
Correct |
552 ms |
1600 KB |
Output is correct |
5 |
Correct |
776 ms |
17416 KB |
Output is correct |
6 |
Correct |
544 ms |
1504 KB |
Output is correct |
7 |
Correct |
346 ms |
1456 KB |
Output is correct |
8 |
Correct |
536 ms |
1760 KB |
Output is correct |
9 |
Correct |
690 ms |
36096 KB |
Output is correct |
10 |
Correct |
714 ms |
36056 KB |
Output is correct |
11 |
Correct |
1162 ms |
61136 KB |
Output is correct |
12 |
Correct |
1006 ms |
53448 KB |
Output is correct |
13 |
Correct |
366 ms |
1344 KB |
Output is correct |
14 |
Correct |
8 ms |
1248 KB |
Output is correct |
15 |
Correct |
824 ms |
1472 KB |
Output is correct |
16 |
Correct |
656 ms |
1600 KB |
Output is correct |
17 |
Correct |
412 ms |
1376 KB |
Output is correct |
18 |
Correct |
746 ms |
17560 KB |
Output is correct |
19 |
Correct |
727 ms |
1536 KB |
Output is correct |
20 |
Correct |
618 ms |
17800 KB |
Output is correct |
21 |
Correct |
502 ms |
1584 KB |
Output is correct |
22 |
Correct |
773 ms |
1624 KB |
Output is correct |
23 |
Correct |
1220 ms |
44232 KB |
Output is correct |
24 |
Correct |
1032 ms |
43696 KB |
Output is correct |
25 |
Correct |
1378 ms |
74936 KB |
Output is correct |
26 |
Correct |
1174 ms |
64528 KB |
Output is correct |
27 |
Correct |
496 ms |
1656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
1400 KB |
Output is correct |
2 |
Correct |
548 ms |
1504 KB |
Output is correct |
3 |
Correct |
708 ms |
23448 KB |
Output is correct |
4 |
Correct |
552 ms |
1600 KB |
Output is correct |
5 |
Correct |
776 ms |
17416 KB |
Output is correct |
6 |
Correct |
544 ms |
1504 KB |
Output is correct |
7 |
Correct |
346 ms |
1456 KB |
Output is correct |
8 |
Correct |
536 ms |
1760 KB |
Output is correct |
9 |
Correct |
690 ms |
36096 KB |
Output is correct |
10 |
Correct |
714 ms |
36056 KB |
Output is correct |
11 |
Correct |
1162 ms |
61136 KB |
Output is correct |
12 |
Correct |
1006 ms |
53448 KB |
Output is correct |
13 |
Correct |
366 ms |
1344 KB |
Output is correct |
14 |
Correct |
8 ms |
1248 KB |
Output is correct |
15 |
Correct |
824 ms |
1472 KB |
Output is correct |
16 |
Correct |
656 ms |
1600 KB |
Output is correct |
17 |
Correct |
412 ms |
1376 KB |
Output is correct |
18 |
Correct |
746 ms |
17560 KB |
Output is correct |
19 |
Correct |
727 ms |
1536 KB |
Output is correct |
20 |
Correct |
618 ms |
17800 KB |
Output is correct |
21 |
Correct |
502 ms |
1584 KB |
Output is correct |
22 |
Correct |
773 ms |
1624 KB |
Output is correct |
23 |
Correct |
1220 ms |
44232 KB |
Output is correct |
24 |
Correct |
1032 ms |
43696 KB |
Output is correct |
25 |
Correct |
1378 ms |
74936 KB |
Output is correct |
26 |
Correct |
1174 ms |
64528 KB |
Output is correct |
27 |
Correct |
496 ms |
1656 KB |
Output is correct |
28 |
Correct |
654 ms |
1504 KB |
Output is correct |
29 |
Correct |
674 ms |
1344 KB |
Output is correct |
30 |
Correct |
1210 ms |
42280 KB |
Output is correct |
31 |
Correct |
754 ms |
1504 KB |
Output is correct |
32 |
Correct |
1158 ms |
37400 KB |
Output is correct |
33 |
Correct |
710 ms |
1400 KB |
Output is correct |
34 |
Correct |
940 ms |
1696 KB |
Output is correct |
35 |
Correct |
804 ms |
1592 KB |
Output is correct |
36 |
Correct |
1226 ms |
48984 KB |
Output is correct |
37 |
Correct |
1286 ms |
49368 KB |
Output is correct |
38 |
Correct |
1760 ms |
85296 KB |
Output is correct |
39 |
Correct |
1364 ms |
78216 KB |
Output is correct |
40 |
Correct |
886 ms |
1600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
944 ms |
1440 KB |
Output is correct |
2 |
Correct |
8 ms |
1368 KB |
Output is correct |
3 |
Correct |
860 ms |
1520 KB |
Output is correct |
4 |
Correct |
1328 ms |
20312 KB |
Output is correct |
5 |
Correct |
74 ms |
1608 KB |
Output is correct |
6 |
Correct |
942 ms |
4128 KB |
Output is correct |
7 |
Correct |
4 ms |
1104 KB |
Output is correct |
8 |
Correct |
1026 ms |
1760 KB |
Output is correct |
9 |
Correct |
968 ms |
1760 KB |
Output is correct |
10 |
Correct |
1693 ms |
55088 KB |
Output is correct |
11 |
Correct |
1538 ms |
48000 KB |
Output is correct |
12 |
Correct |
316 ms |
1248 KB |
Output is correct |
13 |
Correct |
1322 ms |
48384 KB |
Output is correct |
14 |
Correct |
1054 ms |
1384 KB |
Output is correct |
15 |
Correct |
8 ms |
1256 KB |
Output is correct |
16 |
Correct |
1110 ms |
1448 KB |
Output is correct |
17 |
Correct |
966 ms |
1760 KB |
Output is correct |
18 |
Correct |
952 ms |
1832 KB |
Output is correct |
19 |
Correct |
1238 ms |
1544 KB |
Output is correct |
20 |
Correct |
1052 ms |
1504 KB |
Output is correct |
21 |
Correct |
934 ms |
1432 KB |
Output is correct |
22 |
Correct |
1150 ms |
1272 KB |
Output is correct |
23 |
Correct |
1130 ms |
1520 KB |
Output is correct |
24 |
Correct |
550 ms |
1400 KB |
Output is correct |
25 |
Correct |
548 ms |
1504 KB |
Output is correct |
26 |
Correct |
708 ms |
23448 KB |
Output is correct |
27 |
Correct |
552 ms |
1600 KB |
Output is correct |
28 |
Correct |
776 ms |
17416 KB |
Output is correct |
29 |
Correct |
544 ms |
1504 KB |
Output is correct |
30 |
Correct |
346 ms |
1456 KB |
Output is correct |
31 |
Correct |
536 ms |
1760 KB |
Output is correct |
32 |
Correct |
690 ms |
36096 KB |
Output is correct |
33 |
Correct |
714 ms |
36056 KB |
Output is correct |
34 |
Correct |
1162 ms |
61136 KB |
Output is correct |
35 |
Correct |
1006 ms |
53448 KB |
Output is correct |
36 |
Correct |
366 ms |
1344 KB |
Output is correct |
37 |
Correct |
8 ms |
1248 KB |
Output is correct |
38 |
Correct |
824 ms |
1472 KB |
Output is correct |
39 |
Correct |
656 ms |
1600 KB |
Output is correct |
40 |
Correct |
412 ms |
1376 KB |
Output is correct |
41 |
Correct |
746 ms |
17560 KB |
Output is correct |
42 |
Correct |
727 ms |
1536 KB |
Output is correct |
43 |
Correct |
618 ms |
17800 KB |
Output is correct |
44 |
Correct |
502 ms |
1584 KB |
Output is correct |
45 |
Correct |
773 ms |
1624 KB |
Output is correct |
46 |
Correct |
1220 ms |
44232 KB |
Output is correct |
47 |
Correct |
1032 ms |
43696 KB |
Output is correct |
48 |
Correct |
1378 ms |
74936 KB |
Output is correct |
49 |
Correct |
1174 ms |
64528 KB |
Output is correct |
50 |
Correct |
496 ms |
1656 KB |
Output is correct |
51 |
Correct |
654 ms |
1504 KB |
Output is correct |
52 |
Correct |
674 ms |
1344 KB |
Output is correct |
53 |
Correct |
1210 ms |
42280 KB |
Output is correct |
54 |
Correct |
754 ms |
1504 KB |
Output is correct |
55 |
Correct |
1158 ms |
37400 KB |
Output is correct |
56 |
Correct |
710 ms |
1400 KB |
Output is correct |
57 |
Correct |
940 ms |
1696 KB |
Output is correct |
58 |
Correct |
804 ms |
1592 KB |
Output is correct |
59 |
Correct |
1226 ms |
48984 KB |
Output is correct |
60 |
Correct |
1286 ms |
49368 KB |
Output is correct |
61 |
Correct |
1760 ms |
85296 KB |
Output is correct |
62 |
Correct |
1364 ms |
78216 KB |
Output is correct |
63 |
Correct |
886 ms |
1600 KB |
Output is correct |
64 |
Correct |
1550 ms |
2208 KB |
Output is correct |
65 |
Correct |
1612 ms |
46872 KB |
Output is correct |
66 |
Correct |
1772 ms |
40888 KB |
Output is correct |
67 |
Correct |
1132 ms |
2016 KB |
Output is correct |
68 |
Correct |
1062 ms |
1984 KB |
Output is correct |
69 |
Correct |
1912 ms |
83336 KB |
Output is correct |
70 |
Correct |
1701 ms |
68056 KB |
Output is correct |
71 |
Correct |
1286 ms |
8944 KB |
Output is correct |
72 |
Correct |
1166 ms |
2208 KB |
Output is correct |