#include "Azer.h"
#include <vector>
#include <queue>
using namespace std;
namespace{
struct edge{
int v,cost;
bool operator<(const edge &t)const{
return cost>t.cost;
}
};
const int INF=1e9,cnt_cost=9,cnt_v=11;
int N,cnt,cnt_query,receive_cost,receive_v,you_cost,sent_cost;
edge closest;
bool cur_mode;
vector<int> Dist;
vector<bool> Used;
vector<vector<edge>> Edge;
priority_queue<edge> Q;
void my_send(int cnt,int x){
for (int i=0; i<cnt; i++)
SendA(x&(1<<i));
}
edge get_closest(){
while (!Q.empty()){
if (!Used[Q.top().v])
return Q.top();
Q.pop();
}
return {-1,-1};
}
void update_and_send(edge t){
Dist[t.v]=t.cost;
Used[t.v]=true;
if (cnt_query==N-1)
return;
for (edge i:Edge[t.v]){
if (Used[i.v])
continue;
Q.push({i.v,Dist[t.v]+i.cost});
}
closest=get_closest();
if (closest.v==-1)
my_send(cnt_cost,-1);
else
my_send(cnt_cost,closest.cost-sent_cost);
}
}
void InitA(int n,int a,vector<int> u,vector<int> v,vector<int> c){
N=n;
cnt=cnt_query=receive_cost=receive_v=sent_cost=0;
cur_mode=false;
Dist.resize(N);
Used.resize(N);
Edge.resize(N);
for (int i=0; i<N; i++){
Dist[i]=INF;
Used[i]=false;
}
for (int i=0; i<a; i++){
Edge[u[i]].push_back({v[i],c[i]});
Edge[v[i]].push_back({u[i],c[i]});
}
update_and_send({0,0});
}
void ReceiveA(bool x){
if (!cur_mode&&cnt<cnt_cost){
receive_cost+=x*(1<<cnt);
cnt++;
}
if (cur_mode&&cnt<cnt_v){
receive_v+=x*(1<<cnt);
cnt++;
}
if (!cur_mode&&cnt==cnt_cost){
cnt_query++;
if (receive_cost!=(1<<cnt_cost)-1)
you_cost=sent_cost+receive_cost;
if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>=closest.cost){
Q.pop();
my_send(cnt_v,closest.v);
sent_cost=closest.cost;
update_and_send(closest);
}
else{
sent_cost=you_cost;
cur_mode=true;
}
cnt=receive_cost=0;
}
if (cur_mode&&cnt==cnt_v){
update_and_send({receive_v,you_cost});
cnt=receive_v=0;
cur_mode=false;
}
}
vector<int> Answer(){
return Dist;
}
#include "Baijan.h"
#include <vector>
#include <queue>
using namespace std;
namespace{
struct edge{
int v,cost;
bool operator<(const edge &t)const{
return cost>t.cost;
}
};
const int INF=1e9,cnt_cost=9,cnt_v=11;
int N,cnt,receive_cost,receive_v,you_cost,sent_cost;
edge closest;
bool cur_mode;
vector<int> Dist;
vector<bool> Used;
vector<vector<edge>> Edge;
priority_queue<edge> Q;
void my_send(int cnt,int x){
for (int i=0; i<cnt; i++)
SendB(x&(1<<i));
}
edge get_closest(){
while (!Q.empty()){
if (!Used[Q.top().v])
return Q.top();
Q.pop();
}
return {-1,-1};
}
void update_closest(edge t){
Dist[t.v]=t.cost;
Used[t.v]=true;
for (edge i:Edge[t.v]){
if (Used[i.v])
continue;
Q.push({i.v,Dist[t.v]+i.cost});
}
}
}
void InitB(int n,int b,vector<int> s,vector<int> t,vector<int> d){
N=n;
cnt=receive_cost=receive_v=sent_cost=0;
cur_mode=false;
Dist.resize(N);
Used.resize(N);
Edge.resize(N);
for (int i=1; i<N; i++){
Dist[i]=INF;
Used[i]=false;
}
for (int i=0; i<b; i++){
Edge[s[i]].push_back({t[i],d[i]});
Edge[t[i]].push_back({s[i],d[i]});
}
update_closest({0,0});
}
void ReceiveB(bool y){
if (!cur_mode&&cnt<cnt_cost){
receive_cost+=y*(1<<cnt);
cnt++;
}
if (cur_mode&&cnt<cnt_v){
receive_v+=y*(1<<cnt);
cnt++;
}
if (!cur_mode&&cnt==cnt_cost){
if (receive_cost!=(1<<cnt_cost)-1)
you_cost=sent_cost+receive_cost;
closest=get_closest();
if (closest.v==-1)
my_send(cnt_cost,-1);
else
my_send(cnt_cost,closest.cost-sent_cost);
if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>closest.cost){
Q.pop();
update_closest(closest);
sent_cost=closest.cost;
my_send(cnt_v,closest.v);
}
else{
sent_cost=you_cost;
cur_mode=true;
}
cnt=receive_cost=0;
}
if (cur_mode&&cnt==cnt_v){
update_closest({receive_v,you_cost});
cnt=receive_v=0;
cur_mode=false;
}
}
Compilation message
Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:79:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
79 | if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>=closest.cost){
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:76:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
76 | if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>closest.cost){
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
560 ms |
776 KB |
Output is correct |
2 |
Correct |
0 ms |
392 KB |
Output is correct |
3 |
Correct |
548 ms |
776 KB |
Output is correct |
4 |
Correct |
721 ms |
10008 KB |
Output is correct |
5 |
Correct |
31 ms |
780 KB |
Output is correct |
6 |
Correct |
499 ms |
2380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
392 KB |
Output is correct |
2 |
Correct |
582 ms |
720 KB |
Output is correct |
3 |
Correct |
573 ms |
896 KB |
Output is correct |
4 |
Correct |
736 ms |
27704 KB |
Output is correct |
5 |
Correct |
679 ms |
24328 KB |
Output is correct |
6 |
Correct |
121 ms |
524 KB |
Output is correct |
7 |
Correct |
683 ms |
24572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
576 ms |
708 KB |
Output is correct |
2 |
Correct |
0 ms |
392 KB |
Output is correct |
3 |
Correct |
511 ms |
648 KB |
Output is correct |
4 |
Correct |
527 ms |
720 KB |
Output is correct |
5 |
Correct |
466 ms |
716 KB |
Output is correct |
6 |
Correct |
622 ms |
708 KB |
Output is correct |
7 |
Correct |
562 ms |
724 KB |
Output is correct |
8 |
Correct |
457 ms |
768 KB |
Output is correct |
9 |
Correct |
544 ms |
648 KB |
Output is correct |
10 |
Correct |
578 ms |
776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
648 KB |
Output is correct |
2 |
Correct |
249 ms |
600 KB |
Output is correct |
3 |
Correct |
366 ms |
13232 KB |
Output is correct |
4 |
Correct |
272 ms |
648 KB |
Output is correct |
5 |
Correct |
309 ms |
9908 KB |
Output is correct |
6 |
Correct |
276 ms |
648 KB |
Output is correct |
7 |
Correct |
257 ms |
648 KB |
Output is correct |
8 |
Correct |
287 ms |
648 KB |
Output is correct |
9 |
Correct |
372 ms |
19356 KB |
Output is correct |
10 |
Correct |
393 ms |
19516 KB |
Output is correct |
11 |
Correct |
536 ms |
38328 KB |
Output is correct |
12 |
Correct |
469 ms |
35988 KB |
Output is correct |
13 |
Correct |
276 ms |
648 KB |
Output is correct |
14 |
Correct |
1 ms |
392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
648 KB |
Output is correct |
2 |
Correct |
249 ms |
600 KB |
Output is correct |
3 |
Correct |
366 ms |
13232 KB |
Output is correct |
4 |
Correct |
272 ms |
648 KB |
Output is correct |
5 |
Correct |
309 ms |
9908 KB |
Output is correct |
6 |
Correct |
276 ms |
648 KB |
Output is correct |
7 |
Correct |
257 ms |
648 KB |
Output is correct |
8 |
Correct |
287 ms |
648 KB |
Output is correct |
9 |
Correct |
372 ms |
19356 KB |
Output is correct |
10 |
Correct |
393 ms |
19516 KB |
Output is correct |
11 |
Correct |
536 ms |
38328 KB |
Output is correct |
12 |
Correct |
469 ms |
35988 KB |
Output is correct |
13 |
Correct |
276 ms |
648 KB |
Output is correct |
14 |
Correct |
1 ms |
392 KB |
Output is correct |
15 |
Correct |
320 ms |
648 KB |
Output is correct |
16 |
Correct |
262 ms |
520 KB |
Output is correct |
17 |
Correct |
371 ms |
520 KB |
Output is correct |
18 |
Correct |
418 ms |
9996 KB |
Output is correct |
19 |
Correct |
283 ms |
648 KB |
Output is correct |
20 |
Correct |
404 ms |
10176 KB |
Output is correct |
21 |
Correct |
259 ms |
648 KB |
Output is correct |
22 |
Correct |
258 ms |
648 KB |
Output is correct |
23 |
Correct |
513 ms |
22224 KB |
Output is correct |
24 |
Correct |
507 ms |
22416 KB |
Output is correct |
25 |
Correct |
685 ms |
43996 KB |
Output is correct |
26 |
Correct |
614 ms |
40628 KB |
Output is correct |
27 |
Correct |
320 ms |
788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
225 ms |
648 KB |
Output is correct |
2 |
Correct |
249 ms |
600 KB |
Output is correct |
3 |
Correct |
366 ms |
13232 KB |
Output is correct |
4 |
Correct |
272 ms |
648 KB |
Output is correct |
5 |
Correct |
309 ms |
9908 KB |
Output is correct |
6 |
Correct |
276 ms |
648 KB |
Output is correct |
7 |
Correct |
257 ms |
648 KB |
Output is correct |
8 |
Correct |
287 ms |
648 KB |
Output is correct |
9 |
Correct |
372 ms |
19356 KB |
Output is correct |
10 |
Correct |
393 ms |
19516 KB |
Output is correct |
11 |
Correct |
536 ms |
38328 KB |
Output is correct |
12 |
Correct |
469 ms |
35988 KB |
Output is correct |
13 |
Correct |
276 ms |
648 KB |
Output is correct |
14 |
Correct |
1 ms |
392 KB |
Output is correct |
15 |
Correct |
320 ms |
648 KB |
Output is correct |
16 |
Correct |
262 ms |
520 KB |
Output is correct |
17 |
Correct |
371 ms |
520 KB |
Output is correct |
18 |
Correct |
418 ms |
9996 KB |
Output is correct |
19 |
Correct |
283 ms |
648 KB |
Output is correct |
20 |
Correct |
404 ms |
10176 KB |
Output is correct |
21 |
Correct |
259 ms |
648 KB |
Output is correct |
22 |
Correct |
258 ms |
648 KB |
Output is correct |
23 |
Correct |
513 ms |
22224 KB |
Output is correct |
24 |
Correct |
507 ms |
22416 KB |
Output is correct |
25 |
Correct |
685 ms |
43996 KB |
Output is correct |
26 |
Correct |
614 ms |
40628 KB |
Output is correct |
27 |
Correct |
320 ms |
788 KB |
Output is correct |
28 |
Correct |
408 ms |
648 KB |
Output is correct |
29 |
Correct |
350 ms |
620 KB |
Output is correct |
30 |
Correct |
532 ms |
23936 KB |
Output is correct |
31 |
Correct |
422 ms |
640 KB |
Output is correct |
32 |
Correct |
546 ms |
20992 KB |
Output is correct |
33 |
Correct |
372 ms |
708 KB |
Output is correct |
34 |
Correct |
420 ms |
724 KB |
Output is correct |
35 |
Correct |
387 ms |
740 KB |
Output is correct |
36 |
Correct |
603 ms |
24836 KB |
Output is correct |
37 |
Correct |
600 ms |
24980 KB |
Output is correct |
38 |
Correct |
675 ms |
49336 KB |
Output is correct |
39 |
Correct |
685 ms |
46852 KB |
Output is correct |
40 |
Correct |
373 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
560 ms |
776 KB |
Output is correct |
2 |
Correct |
0 ms |
392 KB |
Output is correct |
3 |
Correct |
548 ms |
776 KB |
Output is correct |
4 |
Correct |
721 ms |
10008 KB |
Output is correct |
5 |
Correct |
31 ms |
780 KB |
Output is correct |
6 |
Correct |
499 ms |
2380 KB |
Output is correct |
7 |
Correct |
0 ms |
392 KB |
Output is correct |
8 |
Correct |
582 ms |
720 KB |
Output is correct |
9 |
Correct |
573 ms |
896 KB |
Output is correct |
10 |
Correct |
736 ms |
27704 KB |
Output is correct |
11 |
Correct |
679 ms |
24328 KB |
Output is correct |
12 |
Correct |
121 ms |
524 KB |
Output is correct |
13 |
Correct |
683 ms |
24572 KB |
Output is correct |
14 |
Correct |
576 ms |
708 KB |
Output is correct |
15 |
Correct |
0 ms |
392 KB |
Output is correct |
16 |
Correct |
511 ms |
648 KB |
Output is correct |
17 |
Correct |
527 ms |
720 KB |
Output is correct |
18 |
Correct |
466 ms |
716 KB |
Output is correct |
19 |
Correct |
622 ms |
708 KB |
Output is correct |
20 |
Correct |
562 ms |
724 KB |
Output is correct |
21 |
Correct |
457 ms |
768 KB |
Output is correct |
22 |
Correct |
544 ms |
648 KB |
Output is correct |
23 |
Correct |
578 ms |
776 KB |
Output is correct |
24 |
Correct |
225 ms |
648 KB |
Output is correct |
25 |
Correct |
249 ms |
600 KB |
Output is correct |
26 |
Correct |
366 ms |
13232 KB |
Output is correct |
27 |
Correct |
272 ms |
648 KB |
Output is correct |
28 |
Correct |
309 ms |
9908 KB |
Output is correct |
29 |
Correct |
276 ms |
648 KB |
Output is correct |
30 |
Correct |
257 ms |
648 KB |
Output is correct |
31 |
Correct |
287 ms |
648 KB |
Output is correct |
32 |
Correct |
372 ms |
19356 KB |
Output is correct |
33 |
Correct |
393 ms |
19516 KB |
Output is correct |
34 |
Correct |
536 ms |
38328 KB |
Output is correct |
35 |
Correct |
469 ms |
35988 KB |
Output is correct |
36 |
Correct |
276 ms |
648 KB |
Output is correct |
37 |
Correct |
1 ms |
392 KB |
Output is correct |
38 |
Correct |
320 ms |
648 KB |
Output is correct |
39 |
Correct |
262 ms |
520 KB |
Output is correct |
40 |
Correct |
371 ms |
520 KB |
Output is correct |
41 |
Correct |
418 ms |
9996 KB |
Output is correct |
42 |
Correct |
283 ms |
648 KB |
Output is correct |
43 |
Correct |
404 ms |
10176 KB |
Output is correct |
44 |
Correct |
259 ms |
648 KB |
Output is correct |
45 |
Correct |
258 ms |
648 KB |
Output is correct |
46 |
Correct |
513 ms |
22224 KB |
Output is correct |
47 |
Correct |
507 ms |
22416 KB |
Output is correct |
48 |
Correct |
685 ms |
43996 KB |
Output is correct |
49 |
Correct |
614 ms |
40628 KB |
Output is correct |
50 |
Correct |
320 ms |
788 KB |
Output is correct |
51 |
Correct |
408 ms |
648 KB |
Output is correct |
52 |
Correct |
350 ms |
620 KB |
Output is correct |
53 |
Correct |
532 ms |
23936 KB |
Output is correct |
54 |
Correct |
422 ms |
640 KB |
Output is correct |
55 |
Correct |
546 ms |
20992 KB |
Output is correct |
56 |
Correct |
372 ms |
708 KB |
Output is correct |
57 |
Correct |
420 ms |
724 KB |
Output is correct |
58 |
Correct |
387 ms |
740 KB |
Output is correct |
59 |
Correct |
603 ms |
24836 KB |
Output is correct |
60 |
Correct |
600 ms |
24980 KB |
Output is correct |
61 |
Correct |
675 ms |
49336 KB |
Output is correct |
62 |
Correct |
685 ms |
46852 KB |
Output is correct |
63 |
Correct |
373 ms |
876 KB |
Output is correct |
64 |
Correct |
574 ms |
928 KB |
Output is correct |
65 |
Correct |
823 ms |
26432 KB |
Output is correct |
66 |
Correct |
671 ms |
23360 KB |
Output is correct |
67 |
Correct |
522 ms |
908 KB |
Output is correct |
68 |
Correct |
414 ms |
912 KB |
Output is correct |
69 |
Correct |
921 ms |
48308 KB |
Output is correct |
70 |
Correct |
813 ms |
41332 KB |
Output is correct |
71 |
Correct |
608 ms |
5508 KB |
Output is correct |
72 |
Correct |
591 ms |
1400 KB |
Output is correct |