#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "Azer.h"
vector<pair<int,int>> adj[2001];
int dist[2001];
int vis[2001];
int num=0;
int cur=0;
int st=0;
int last=0;
pair<int,int> best;
int num2=0;
int cur2=0;
int n;
vector<int> Answer(){
vector<int> ans2;
for(int i=0;i<n;i++){
ans2.pb(dist[i]);
}
return ans2;
}
void ReceiveA(bool x){
if(st==0){
if(x){
num+=(1<<cur);
}
cur+=1;
if(cur==9){
cur=0;
st=1;
}
else{
return;
}
//cout<<cur<<"<"<<num<<endl;
}
if(st==1){
for(auto j:adj[last]){
if(dist[j.a]==-1 or dist[j.a]>dist[last]+j.b){
dist[j.a]=dist[last]+j.b;
}
}
best={-1,-1};
for(int i=0;i<n;i++){
// //cout<<i<<":::"<<dist[i]<<endl;
if(vis[i]==0 and dist[i]!=-1){
if(best.a==-1){
best={dist[i],i};
}
else{
if(dist[i]<best.a){
best={dist[i],i};
}
}
}
}
if(best.a==-1){
best.a=dist[last]+511;
}
//cout<<best.a<<"::"<<best.b<<"::"<<num<<endl;
/* if(num==0){
SendA(0);
st=3;
}
else if(best.a==-1){
SendA(1);
st=2;
}*/
if(best.a<num){
// SendA(0);
/* for(int i=0;i<9;i++){
if((1<<i)&(best.a-dist[last])){
SendA(1);
}
else{
SendA(0);
}
}*/
st=3;
}
else{
for(int i=0;i<9;i++){
SendA(1);
}
//SendA(1);
st=2;
}
//cout<<st<<"....."<<endl;
if(st==2){
return;
}
}
if(st==2){
if(x){
num2+=(1<<cur2);
}
cur2+=1;
//cout<<cur2<<";;;;;;;;;;;;;;;"<<endl;
if(cur2==11){
last=num2;
//cout<<num2<<"//"<<endl;
vis[last]=1;
dist[last]=num;
}
else{
return;
}
}
if(st==3){
dist[best.b]=best.a;
vis[best.b]=1;
if(dist[last]>best.a){
while(true){
continue;
}
}
for(int i=0;i<9;i++){
if((1<<i)&(best.a-dist[last])){
SendA(1);
}
else{
SendA(0);
}
}
for(int i=0;i<11;i++){
if((1<<i)&best.b){
SendA(1);
}
else{
SendA(0);
}
}
last=best.b;
}
//cout<<last<<','<<dist[last]<<endl;
st=0;
num=dist[last];
num2=0;
cur2=0;
cur=0;
/* int kk=0;
for(int i=0;i<n;i++){
if(vis[i]==0){
kk=1;
}
}
if(kk){
SendA(0);
}*/
}
void InitA(int nn,int m,vector<int> aa,vector<int> bb,vector<int> cc){
n=nn;
for(int i=0;i<m;i++){
adj[aa[i]].pb({bb[i],cc[i]});
adj[bb[i]].pb({aa[i],cc[i]});
}
for(int i=1;i<n;i++){
dist[i]=-1;
}
vis[0]=1;
//SendA(0);
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "Baijan.h"
vector<pair<int,int>> adj2[2001];
int dist2[2001];
int st2=0;
int last2=0;
int vis2[2001];
pair<int,int> best2;
int ne;
int cur3=0;
int cur4=0;
int num3=0;
int num4=0;
void ReceiveB(bool x){
if(st2==0){
for(auto j:adj2[last2]){
if(dist2[j.a]==-1 or dist2[j.a]>dist2[last2]+j.b){
dist2[j.a]=dist2[last2]+j.b;
}
}
best2={-1,-1};
for(int i=0;i<ne;i++){
if(vis2[i]==0 and dist2[i]!=-1){
if(best2.a==-1){
best2={dist2[i],i};
}
else{
if(dist2[i]<best2.a){
best2={dist2[i],i};
}
}
}
}
if(best2.a==-1){
best2.a=dist2[last2]+511;
}
//cout<<best2.a<<"::"<<best2.b<<endl;
// best2.a=max(best2.a,0);
if(best2.a<dist2[last2]){
while(true){
continue;
}
}
for(int i=0;i<9;i++){
if((1<<i)&(best2.a-dist2[last2])){
SendB(1);
}
else{
SendB(0);
}
}
st2=3;
return;
}
/* if(st2==1){
if(x){
st2=2;
}
else{
st2=3;
return;
}
}*/
if(st2==2){
//cout<<1111<<endl;
}
if(st2==3){
if(cur3==0){
num3+=(dist2[last2]);
}
if(cur3<9){
if(x){
num3+=(1<<cur3);
}
cur3++;
if(num3-dist2[last2]==511){
st2=0;
dist2[best2.b]=best2.a;
vis2[best2.b]=1;
last2=best2.b;
// cout<<111<<endl;
for(int i=0;i<11;i++){
if((1<<i)&best2.b){
SendB(1);
}
else{
SendB(0);
}
}
}
else{
return;
}
}
else{
if(x){
num4+=(1<<cur4);
}
cur4++;
if(cur4==11){
//cout<<20<<endl;
//cout<<num4<<",,"<<num3<<endl;
dist2[num4]=num3;
vis2[num4]=1;
last2=num4;
}
else{
return;
}
}
}
// //cout<<last2<<"<<<>>>>"<<endl;
num3=0;
num4=0;
cur3=0;
cur4=0;
st2=0;
int kk=0;
for(int i=0;i<ne;i++){
if(vis2[i]==0){
kk=1;
}
}
if(kk){
ReceiveB(0);
}
}
void InitB(int nn,int m,vector<int> aa,vector<int> bb,vector<int> cc){
ne=nn;
for(int i=0;i<m;i++){
adj2[aa[i]].pb({bb[i],cc[i]});
adj2[bb[i]].pb({aa[i],cc[i]});
}
for(int i=1;i<ne;i++){
dist2[i]=-1;
}
vis2[0]=1;
ReceiveB(0);
}
/*int main(){
ios_base::sync_with_st2dio(false);
cin.tie(NULL);
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1278 ms |
1856 KB |
Output is correct |
2 |
Correct |
18 ms |
1536 KB |
Output is correct |
3 |
Correct |
1148 ms |
1816 KB |
Output is correct |
4 |
Correct |
1190 ms |
20448 KB |
Output is correct |
5 |
Correct |
96 ms |
1792 KB |
Output is correct |
6 |
Correct |
1104 ms |
5056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1536 KB |
Output is correct |
2 |
Correct |
1274 ms |
2048 KB |
Output is correct |
3 |
Correct |
1144 ms |
1792 KB |
Output is correct |
4 |
Correct |
1218 ms |
55264 KB |
Output is correct |
5 |
Correct |
1470 ms |
48352 KB |
Output is correct |
6 |
Correct |
308 ms |
1536 KB |
Output is correct |
7 |
Correct |
1604 ms |
48608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1071 ms |
1960 KB |
Output is correct |
2 |
Correct |
16 ms |
1536 KB |
Output is correct |
3 |
Correct |
1270 ms |
1536 KB |
Output is correct |
4 |
Correct |
1158 ms |
2048 KB |
Output is correct |
5 |
Correct |
1262 ms |
2016 KB |
Output is correct |
6 |
Correct |
1272 ms |
1960 KB |
Output is correct |
7 |
Correct |
1178 ms |
1792 KB |
Output is correct |
8 |
Correct |
1238 ms |
1536 KB |
Output is correct |
9 |
Correct |
1026 ms |
1792 KB |
Output is correct |
10 |
Correct |
1250 ms |
1768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
564 ms |
1952 KB |
Output is correct |
2 |
Correct |
502 ms |
1760 KB |
Output is correct |
3 |
Correct |
682 ms |
24056 KB |
Output is correct |
4 |
Correct |
590 ms |
1792 KB |
Output is correct |
5 |
Correct |
620 ms |
17464 KB |
Output is correct |
6 |
Correct |
476 ms |
1792 KB |
Output is correct |
7 |
Correct |
434 ms |
1792 KB |
Output is correct |
8 |
Correct |
444 ms |
1792 KB |
Output is correct |
9 |
Correct |
758 ms |
36008 KB |
Output is correct |
10 |
Correct |
712 ms |
36408 KB |
Output is correct |
11 |
Correct |
1152 ms |
61360 KB |
Output is correct |
12 |
Correct |
972 ms |
53936 KB |
Output is correct |
13 |
Correct |
438 ms |
1792 KB |
Output is correct |
14 |
Correct |
18 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
564 ms |
1952 KB |
Output is correct |
2 |
Correct |
502 ms |
1760 KB |
Output is correct |
3 |
Correct |
682 ms |
24056 KB |
Output is correct |
4 |
Correct |
590 ms |
1792 KB |
Output is correct |
5 |
Correct |
620 ms |
17464 KB |
Output is correct |
6 |
Correct |
476 ms |
1792 KB |
Output is correct |
7 |
Correct |
434 ms |
1792 KB |
Output is correct |
8 |
Correct |
444 ms |
1792 KB |
Output is correct |
9 |
Correct |
758 ms |
36008 KB |
Output is correct |
10 |
Correct |
712 ms |
36408 KB |
Output is correct |
11 |
Correct |
1152 ms |
61360 KB |
Output is correct |
12 |
Correct |
972 ms |
53936 KB |
Output is correct |
13 |
Correct |
438 ms |
1792 KB |
Output is correct |
14 |
Correct |
18 ms |
1536 KB |
Output is correct |
15 |
Correct |
624 ms |
1584 KB |
Output is correct |
16 |
Correct |
780 ms |
1600 KB |
Output is correct |
17 |
Correct |
484 ms |
1616 KB |
Output is correct |
18 |
Correct |
1038 ms |
17688 KB |
Output is correct |
19 |
Correct |
580 ms |
1872 KB |
Output is correct |
20 |
Correct |
848 ms |
18232 KB |
Output is correct |
21 |
Correct |
552 ms |
1704 KB |
Output is correct |
22 |
Correct |
544 ms |
1608 KB |
Output is correct |
23 |
Correct |
1024 ms |
44096 KB |
Output is correct |
24 |
Correct |
878 ms |
43976 KB |
Output is correct |
25 |
Correct |
1570 ms |
75128 KB |
Output is correct |
26 |
Correct |
1190 ms |
64368 KB |
Output is correct |
27 |
Correct |
758 ms |
2024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
564 ms |
1952 KB |
Output is correct |
2 |
Correct |
502 ms |
1760 KB |
Output is correct |
3 |
Correct |
682 ms |
24056 KB |
Output is correct |
4 |
Correct |
590 ms |
1792 KB |
Output is correct |
5 |
Correct |
620 ms |
17464 KB |
Output is correct |
6 |
Correct |
476 ms |
1792 KB |
Output is correct |
7 |
Correct |
434 ms |
1792 KB |
Output is correct |
8 |
Correct |
444 ms |
1792 KB |
Output is correct |
9 |
Correct |
758 ms |
36008 KB |
Output is correct |
10 |
Correct |
712 ms |
36408 KB |
Output is correct |
11 |
Correct |
1152 ms |
61360 KB |
Output is correct |
12 |
Correct |
972 ms |
53936 KB |
Output is correct |
13 |
Correct |
438 ms |
1792 KB |
Output is correct |
14 |
Correct |
18 ms |
1536 KB |
Output is correct |
15 |
Correct |
624 ms |
1584 KB |
Output is correct |
16 |
Correct |
780 ms |
1600 KB |
Output is correct |
17 |
Correct |
484 ms |
1616 KB |
Output is correct |
18 |
Correct |
1038 ms |
17688 KB |
Output is correct |
19 |
Correct |
580 ms |
1872 KB |
Output is correct |
20 |
Correct |
848 ms |
18232 KB |
Output is correct |
21 |
Correct |
552 ms |
1704 KB |
Output is correct |
22 |
Correct |
544 ms |
1608 KB |
Output is correct |
23 |
Correct |
1024 ms |
44096 KB |
Output is correct |
24 |
Correct |
878 ms |
43976 KB |
Output is correct |
25 |
Correct |
1570 ms |
75128 KB |
Output is correct |
26 |
Correct |
1190 ms |
64368 KB |
Output is correct |
27 |
Correct |
758 ms |
2024 KB |
Output is correct |
28 |
Correct |
842 ms |
1792 KB |
Output is correct |
29 |
Correct |
858 ms |
1760 KB |
Output is correct |
30 |
Correct |
1315 ms |
42152 KB |
Output is correct |
31 |
Correct |
904 ms |
1536 KB |
Output is correct |
32 |
Correct |
1194 ms |
37536 KB |
Output is correct |
33 |
Correct |
812 ms |
1536 KB |
Output is correct |
34 |
Correct |
650 ms |
2200 KB |
Output is correct |
35 |
Correct |
908 ms |
2272 KB |
Output is correct |
36 |
Correct |
888 ms |
49640 KB |
Output is correct |
37 |
Correct |
1002 ms |
49088 KB |
Output is correct |
38 |
Correct |
1650 ms |
86040 KB |
Output is correct |
39 |
Correct |
1614 ms |
78664 KB |
Output is correct |
40 |
Correct |
824 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1278 ms |
1856 KB |
Output is correct |
2 |
Correct |
18 ms |
1536 KB |
Output is correct |
3 |
Correct |
1148 ms |
1816 KB |
Output is correct |
4 |
Correct |
1190 ms |
20448 KB |
Output is correct |
5 |
Correct |
96 ms |
1792 KB |
Output is correct |
6 |
Correct |
1104 ms |
5056 KB |
Output is correct |
7 |
Correct |
18 ms |
1536 KB |
Output is correct |
8 |
Correct |
1274 ms |
2048 KB |
Output is correct |
9 |
Correct |
1144 ms |
1792 KB |
Output is correct |
10 |
Correct |
1218 ms |
55264 KB |
Output is correct |
11 |
Correct |
1470 ms |
48352 KB |
Output is correct |
12 |
Correct |
308 ms |
1536 KB |
Output is correct |
13 |
Correct |
1604 ms |
48608 KB |
Output is correct |
14 |
Correct |
1071 ms |
1960 KB |
Output is correct |
15 |
Correct |
16 ms |
1536 KB |
Output is correct |
16 |
Correct |
1270 ms |
1536 KB |
Output is correct |
17 |
Correct |
1158 ms |
2048 KB |
Output is correct |
18 |
Correct |
1262 ms |
2016 KB |
Output is correct |
19 |
Correct |
1272 ms |
1960 KB |
Output is correct |
20 |
Correct |
1178 ms |
1792 KB |
Output is correct |
21 |
Correct |
1238 ms |
1536 KB |
Output is correct |
22 |
Correct |
1026 ms |
1792 KB |
Output is correct |
23 |
Correct |
1250 ms |
1768 KB |
Output is correct |
24 |
Correct |
564 ms |
1952 KB |
Output is correct |
25 |
Correct |
502 ms |
1760 KB |
Output is correct |
26 |
Correct |
682 ms |
24056 KB |
Output is correct |
27 |
Correct |
590 ms |
1792 KB |
Output is correct |
28 |
Correct |
620 ms |
17464 KB |
Output is correct |
29 |
Correct |
476 ms |
1792 KB |
Output is correct |
30 |
Correct |
434 ms |
1792 KB |
Output is correct |
31 |
Correct |
444 ms |
1792 KB |
Output is correct |
32 |
Correct |
758 ms |
36008 KB |
Output is correct |
33 |
Correct |
712 ms |
36408 KB |
Output is correct |
34 |
Correct |
1152 ms |
61360 KB |
Output is correct |
35 |
Correct |
972 ms |
53936 KB |
Output is correct |
36 |
Correct |
438 ms |
1792 KB |
Output is correct |
37 |
Correct |
18 ms |
1536 KB |
Output is correct |
38 |
Correct |
624 ms |
1584 KB |
Output is correct |
39 |
Correct |
780 ms |
1600 KB |
Output is correct |
40 |
Correct |
484 ms |
1616 KB |
Output is correct |
41 |
Correct |
1038 ms |
17688 KB |
Output is correct |
42 |
Correct |
580 ms |
1872 KB |
Output is correct |
43 |
Correct |
848 ms |
18232 KB |
Output is correct |
44 |
Correct |
552 ms |
1704 KB |
Output is correct |
45 |
Correct |
544 ms |
1608 KB |
Output is correct |
46 |
Correct |
1024 ms |
44096 KB |
Output is correct |
47 |
Correct |
878 ms |
43976 KB |
Output is correct |
48 |
Correct |
1570 ms |
75128 KB |
Output is correct |
49 |
Correct |
1190 ms |
64368 KB |
Output is correct |
50 |
Correct |
758 ms |
2024 KB |
Output is correct |
51 |
Correct |
842 ms |
1792 KB |
Output is correct |
52 |
Correct |
858 ms |
1760 KB |
Output is correct |
53 |
Correct |
1315 ms |
42152 KB |
Output is correct |
54 |
Correct |
904 ms |
1536 KB |
Output is correct |
55 |
Correct |
1194 ms |
37536 KB |
Output is correct |
56 |
Correct |
812 ms |
1536 KB |
Output is correct |
57 |
Correct |
650 ms |
2200 KB |
Output is correct |
58 |
Correct |
908 ms |
2272 KB |
Output is correct |
59 |
Correct |
888 ms |
49640 KB |
Output is correct |
60 |
Correct |
1002 ms |
49088 KB |
Output is correct |
61 |
Correct |
1650 ms |
86040 KB |
Output is correct |
62 |
Correct |
1614 ms |
78664 KB |
Output is correct |
63 |
Correct |
824 ms |
2048 KB |
Output is correct |
64 |
Correct |
1078 ms |
2048 KB |
Output is correct |
65 |
Correct |
1594 ms |
47016 KB |
Output is correct |
66 |
Correct |
1186 ms |
41072 KB |
Output is correct |
67 |
Correct |
1280 ms |
2048 KB |
Output is correct |
68 |
Correct |
888 ms |
2248 KB |
Output is correct |
69 |
Correct |
1680 ms |
83584 KB |
Output is correct |
70 |
Correct |
1849 ms |
68144 KB |
Output is correct |
71 |
Correct |
1114 ms |
9152 KB |
Output is correct |
72 |
Correct |
1092 ms |
2304 KB |
Output is correct |