#include "Azer.h"
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstdio>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef pair < int, int > pii;
namespace {
const int N = 2005;
int n;
vector < pii > v[N];
int dis[N], mks, bio[N];
int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
pii tmp; int cv, brj;
void obradi(int x){
mks = max(mks, dis[x]);
bio[x] = 1; // printf("A: obradujem %d\n", x);
for(pii nxt : v[x]){
if(dis[nxt.X] == -1 || dis[x] + nxt.Y < dis[nxt.X])
dis[nxt.X] = dis[x] + nxt.Y;
}
}
pii nadi_najblizeg(){
int bst = 0, dod = mks + 501;
for(int i = 0;i < n;i++){
if(bio[i] || dis[i] == -1) continue;
if(!bst || dis[i] < dod)
bst = i, dod = dis[i];
}
tko = !!((cnt * (mks + n)) & 8);
return {bst, dod - mks};
}
void posalji_broj(int x, int ln){
//printf("A: saljem %d u %d\n", x, ln);
for(int i = ln - 1;i >= 0;i--)
SendA(!!(x & (1 << i)));
}
void korak(){
tmp = nadi_najblizeg();
cv = tmp.X, brj = tmp.Y;
//printf("A: radim korak tko = %d\n", tko);
//printf("A : cv = %d brj = %d\n", cv, brj);
if(tko){
sto = 1; jos = 1; ret = 0;
posalji_broj(brj, 9);
}
else{
sto = 4; jos = 9; ret = 0;
}
}
}
void InitA(int n, int a, vi U, vi V, vi C) {
::n = n;
for(int i = 0;i < a;i++){
v[U[i]].PB({V[i], C[i]});
v[V[i]].PB({U[i], C[i]});
}
for(int i = 0; i < n;i++)
dis[i] = -1;
dis[0] = 0; cnt++; obradi(0);
if(n != 1)
SendA(0);
Answer();
}
void ReceiveA(bool x) {
if(sto == 0) {
korak(); return;
}
ret = 2 * ret + x; jos--;
//printf("B: jos = %d ret = %d sto = %d\n", jos, ret, sto);
if(jos != 0) return;
if(sto == 1){
if(ret){
//printf("tu sam\n");
jos = 9;
sto = 2;
ret = 0;
}
else{
posalji_broj(cv, 11);
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
}
else if(sto == 2){
brj = ret; ret = 0;
jos = 11;
sto = 3;
}
else if(sto == 3){
cv = ret; ret = 0;
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
else if(sto == 4){
brj2 = ret; ret = 0;
if(brj2 <= brj){
brj = brj2;
sto = 5; jos = 11; ret = 0;
posalji_broj(0, 1);
}
else{
posalji_broj(1, 1);
posalji_broj(brj, 9);
posalji_broj(cv, 11);
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
}
else if(sto == 5){
cv = ret; ret = 0;
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
}
vi Answer() {
vi ans(n);
for (int k = 0; k < n; ++k) {
ans[k] = dis[k];
}
return ans;
}
#include "Baijan.h"
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstdio>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef vector < int > vi;
typedef pair < int, int > pii;
namespace {
const int N = 2005;
int n;
vector < pii > v[N];
int dis[N], mks, bio[N];
int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
pii tmp; int cv, brj;
void obradi(int x){
mks = max(mks, dis[x]);
bio[x] = 1; //printf("B: obradujem %d\n", x);
for(pii nxt : v[x]){
if(dis[nxt.X] == -1 || dis[x] + nxt.Y < dis[nxt.X])
dis[nxt.X] = dis[x] + nxt.Y;
}
}
pii nadi_najblizeg(){
int bst = 0, dod = mks + 501;
for(int i = 0;i < n;i++){
if(bio[i] || dis[i] == -1)
continue;
if(!bst || dis[i] < dod)
bst = i, dod = dis[i];
}
tko = !((cnt * (mks + n)) & 8);
return {bst, dod - mks};
}
void posalji_broj(int x, int ln){
//printf("B: saljem %d u %d\n", x, ln);
for(int i = ln - 1;i >= 0;i--)
SendB(!!(x & (1 << i)));
}
void korak(){
tmp = nadi_najblizeg();
cv = tmp.X, brj = tmp.Y;
//printf("B: radim korak tko = %d\n", tko);
//printf("B : cv = %d brj = %d\n", cv, brj);
if(tko){
sto = 1; jos = 1; ret = 0;
posalji_broj(brj, 9);
}
else{
sto = 4; jos = 9; ret = 0;
}
}
}
void InitB(int n, int a, vi U, vi V, vi C) {
::n = n;
for(int i = 0;i < a;i++){
v[U[i]].PB({V[i], C[i]});
v[V[i]].PB({U[i], C[i]});
}
for(int i = 0; i < n;i++)
dis[i] = -1;
dis[0] = 0; cnt++; obradi(0);
if(n != 1)
SendB(0);
}
void ReceiveB(bool x) {
if(sto == 0) {
korak(); return;
}
ret = 2 * ret + x; jos--;
//printf("B: jos = %d ret = %d sto = %d\n", jos, ret, sto);
if(jos != 0) return;
if(sto == 1){
if(ret){
//printf("tu sam\n");
jos = 9;
sto = 2;
ret = 0;
}
else{
posalji_broj(cv, 11);
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
}
else if(sto == 2){
brj = ret; ret = 0;
jos = 11;
sto = 3;
}
else if(sto == 3){
cv = ret; ret = 0;
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
else if(sto == 4){
brj2 = ret; ret = 0;
if(brj2 <= brj){
brj = brj2;
sto = 5; jos = 11; ret = 0;
posalji_broj(0, 1);
}
else{
posalji_broj(1, 1);
posalji_broj(brj, 9);
posalji_broj(cv, 11);
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
}
else if(sto == 5){
cv = ret; ret = 0;
dis[cv] = mks + brj;
obradi(cv);
if((++cnt) != n)
korak();
}
}
Compilation message
Azer.cpp:23:14: warning: '{anonymous}::kolko' defined but not used [-Wunused-variable]
23 | int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
| ^~~~~
Baijan.cpp:23:14: warning: '{anonymous}::kolko' defined but not used [-Wunused-variable]
23 | int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
906 ms |
1536 KB |
Output is correct |
2 |
Correct |
2 ms |
1536 KB |
Output is correct |
3 |
Correct |
828 ms |
1760 KB |
Output is correct |
4 |
Correct |
1042 ms |
20208 KB |
Output is correct |
5 |
Correct |
54 ms |
1792 KB |
Output is correct |
6 |
Correct |
980 ms |
4832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1280 KB |
Output is correct |
2 |
Correct |
872 ms |
1536 KB |
Output is correct |
3 |
Correct |
948 ms |
1792 KB |
Output is correct |
4 |
Correct |
1101 ms |
55264 KB |
Output is correct |
5 |
Correct |
1362 ms |
48104 KB |
Output is correct |
6 |
Correct |
146 ms |
1600 KB |
Output is correct |
7 |
Correct |
1310 ms |
48352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
932 ms |
1536 KB |
Output is correct |
2 |
Correct |
2 ms |
1280 KB |
Output is correct |
3 |
Correct |
894 ms |
1536 KB |
Output is correct |
4 |
Correct |
830 ms |
1536 KB |
Output is correct |
5 |
Correct |
984 ms |
1640 KB |
Output is correct |
6 |
Correct |
816 ms |
1536 KB |
Output is correct |
7 |
Correct |
938 ms |
1536 KB |
Output is correct |
8 |
Correct |
804 ms |
1760 KB |
Output is correct |
9 |
Correct |
872 ms |
1536 KB |
Output is correct |
10 |
Correct |
826 ms |
1760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
1536 KB |
Output is correct |
2 |
Correct |
438 ms |
1536 KB |
Output is correct |
3 |
Correct |
621 ms |
23552 KB |
Output is correct |
4 |
Correct |
434 ms |
1536 KB |
Output is correct |
5 |
Correct |
512 ms |
17456 KB |
Output is correct |
6 |
Correct |
330 ms |
1640 KB |
Output is correct |
7 |
Correct |
434 ms |
1536 KB |
Output is correct |
8 |
Correct |
404 ms |
1536 KB |
Output is correct |
9 |
Correct |
688 ms |
36248 KB |
Output is correct |
10 |
Correct |
658 ms |
36064 KB |
Output is correct |
11 |
Correct |
1038 ms |
61360 KB |
Output is correct |
12 |
Correct |
780 ms |
53848 KB |
Output is correct |
13 |
Correct |
314 ms |
1752 KB |
Output is correct |
14 |
Correct |
2 ms |
1536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
1536 KB |
Output is correct |
2 |
Correct |
438 ms |
1536 KB |
Output is correct |
3 |
Correct |
621 ms |
23552 KB |
Output is correct |
4 |
Correct |
434 ms |
1536 KB |
Output is correct |
5 |
Correct |
512 ms |
17456 KB |
Output is correct |
6 |
Correct |
330 ms |
1640 KB |
Output is correct |
7 |
Correct |
434 ms |
1536 KB |
Output is correct |
8 |
Correct |
404 ms |
1536 KB |
Output is correct |
9 |
Correct |
688 ms |
36248 KB |
Output is correct |
10 |
Correct |
658 ms |
36064 KB |
Output is correct |
11 |
Correct |
1038 ms |
61360 KB |
Output is correct |
12 |
Correct |
780 ms |
53848 KB |
Output is correct |
13 |
Correct |
314 ms |
1752 KB |
Output is correct |
14 |
Correct |
2 ms |
1536 KB |
Output is correct |
15 |
Correct |
418 ms |
1576 KB |
Output is correct |
16 |
Correct |
482 ms |
1440 KB |
Output is correct |
17 |
Correct |
494 ms |
1280 KB |
Output is correct |
18 |
Correct |
609 ms |
17600 KB |
Output is correct |
19 |
Correct |
418 ms |
1704 KB |
Output is correct |
20 |
Correct |
592 ms |
17992 KB |
Output is correct |
21 |
Correct |
428 ms |
1760 KB |
Output is correct |
22 |
Correct |
408 ms |
2016 KB |
Output is correct |
23 |
Correct |
958 ms |
44264 KB |
Output is correct |
24 |
Correct |
880 ms |
43984 KB |
Output is correct |
25 |
Correct |
1230 ms |
74736 KB |
Output is correct |
26 |
Correct |
1142 ms |
64488 KB |
Output is correct |
27 |
Correct |
412 ms |
1816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
420 ms |
1536 KB |
Output is correct |
2 |
Correct |
438 ms |
1536 KB |
Output is correct |
3 |
Correct |
621 ms |
23552 KB |
Output is correct |
4 |
Correct |
434 ms |
1536 KB |
Output is correct |
5 |
Correct |
512 ms |
17456 KB |
Output is correct |
6 |
Correct |
330 ms |
1640 KB |
Output is correct |
7 |
Correct |
434 ms |
1536 KB |
Output is correct |
8 |
Correct |
404 ms |
1536 KB |
Output is correct |
9 |
Correct |
688 ms |
36248 KB |
Output is correct |
10 |
Correct |
658 ms |
36064 KB |
Output is correct |
11 |
Correct |
1038 ms |
61360 KB |
Output is correct |
12 |
Correct |
780 ms |
53848 KB |
Output is correct |
13 |
Correct |
314 ms |
1752 KB |
Output is correct |
14 |
Correct |
2 ms |
1536 KB |
Output is correct |
15 |
Correct |
418 ms |
1576 KB |
Output is correct |
16 |
Correct |
482 ms |
1440 KB |
Output is correct |
17 |
Correct |
494 ms |
1280 KB |
Output is correct |
18 |
Correct |
609 ms |
17600 KB |
Output is correct |
19 |
Correct |
418 ms |
1704 KB |
Output is correct |
20 |
Correct |
592 ms |
17992 KB |
Output is correct |
21 |
Correct |
428 ms |
1760 KB |
Output is correct |
22 |
Correct |
408 ms |
2016 KB |
Output is correct |
23 |
Correct |
958 ms |
44264 KB |
Output is correct |
24 |
Correct |
880 ms |
43984 KB |
Output is correct |
25 |
Correct |
1230 ms |
74736 KB |
Output is correct |
26 |
Correct |
1142 ms |
64488 KB |
Output is correct |
27 |
Correct |
412 ms |
1816 KB |
Output is correct |
28 |
Correct |
586 ms |
1696 KB |
Output is correct |
29 |
Correct |
650 ms |
1368 KB |
Output is correct |
30 |
Correct |
1014 ms |
42200 KB |
Output is correct |
31 |
Correct |
546 ms |
1704 KB |
Output is correct |
32 |
Correct |
794 ms |
37584 KB |
Output is correct |
33 |
Correct |
719 ms |
1560 KB |
Output is correct |
34 |
Correct |
600 ms |
1736 KB |
Output is correct |
35 |
Correct |
712 ms |
1712 KB |
Output is correct |
36 |
Correct |
1208 ms |
49144 KB |
Output is correct |
37 |
Correct |
1236 ms |
49176 KB |
Output is correct |
38 |
Correct |
1402 ms |
85656 KB |
Output is correct |
39 |
Correct |
1230 ms |
78632 KB |
Output is correct |
40 |
Correct |
664 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
906 ms |
1536 KB |
Output is correct |
2 |
Correct |
2 ms |
1536 KB |
Output is correct |
3 |
Correct |
828 ms |
1760 KB |
Output is correct |
4 |
Correct |
1042 ms |
20208 KB |
Output is correct |
5 |
Correct |
54 ms |
1792 KB |
Output is correct |
6 |
Correct |
980 ms |
4832 KB |
Output is correct |
7 |
Correct |
2 ms |
1280 KB |
Output is correct |
8 |
Correct |
872 ms |
1536 KB |
Output is correct |
9 |
Correct |
948 ms |
1792 KB |
Output is correct |
10 |
Correct |
1101 ms |
55264 KB |
Output is correct |
11 |
Correct |
1362 ms |
48104 KB |
Output is correct |
12 |
Correct |
146 ms |
1600 KB |
Output is correct |
13 |
Correct |
1310 ms |
48352 KB |
Output is correct |
14 |
Correct |
932 ms |
1536 KB |
Output is correct |
15 |
Correct |
2 ms |
1280 KB |
Output is correct |
16 |
Correct |
894 ms |
1536 KB |
Output is correct |
17 |
Correct |
830 ms |
1536 KB |
Output is correct |
18 |
Correct |
984 ms |
1640 KB |
Output is correct |
19 |
Correct |
816 ms |
1536 KB |
Output is correct |
20 |
Correct |
938 ms |
1536 KB |
Output is correct |
21 |
Correct |
804 ms |
1760 KB |
Output is correct |
22 |
Correct |
872 ms |
1536 KB |
Output is correct |
23 |
Correct |
826 ms |
1760 KB |
Output is correct |
24 |
Correct |
420 ms |
1536 KB |
Output is correct |
25 |
Correct |
438 ms |
1536 KB |
Output is correct |
26 |
Correct |
621 ms |
23552 KB |
Output is correct |
27 |
Correct |
434 ms |
1536 KB |
Output is correct |
28 |
Correct |
512 ms |
17456 KB |
Output is correct |
29 |
Correct |
330 ms |
1640 KB |
Output is correct |
30 |
Correct |
434 ms |
1536 KB |
Output is correct |
31 |
Correct |
404 ms |
1536 KB |
Output is correct |
32 |
Correct |
688 ms |
36248 KB |
Output is correct |
33 |
Correct |
658 ms |
36064 KB |
Output is correct |
34 |
Correct |
1038 ms |
61360 KB |
Output is correct |
35 |
Correct |
780 ms |
53848 KB |
Output is correct |
36 |
Correct |
314 ms |
1752 KB |
Output is correct |
37 |
Correct |
2 ms |
1536 KB |
Output is correct |
38 |
Correct |
418 ms |
1576 KB |
Output is correct |
39 |
Correct |
482 ms |
1440 KB |
Output is correct |
40 |
Correct |
494 ms |
1280 KB |
Output is correct |
41 |
Correct |
609 ms |
17600 KB |
Output is correct |
42 |
Correct |
418 ms |
1704 KB |
Output is correct |
43 |
Correct |
592 ms |
17992 KB |
Output is correct |
44 |
Correct |
428 ms |
1760 KB |
Output is correct |
45 |
Correct |
408 ms |
2016 KB |
Output is correct |
46 |
Correct |
958 ms |
44264 KB |
Output is correct |
47 |
Correct |
880 ms |
43984 KB |
Output is correct |
48 |
Correct |
1230 ms |
74736 KB |
Output is correct |
49 |
Correct |
1142 ms |
64488 KB |
Output is correct |
50 |
Correct |
412 ms |
1816 KB |
Output is correct |
51 |
Correct |
586 ms |
1696 KB |
Output is correct |
52 |
Correct |
650 ms |
1368 KB |
Output is correct |
53 |
Correct |
1014 ms |
42200 KB |
Output is correct |
54 |
Correct |
546 ms |
1704 KB |
Output is correct |
55 |
Correct |
794 ms |
37584 KB |
Output is correct |
56 |
Correct |
719 ms |
1560 KB |
Output is correct |
57 |
Correct |
600 ms |
1736 KB |
Output is correct |
58 |
Correct |
712 ms |
1712 KB |
Output is correct |
59 |
Correct |
1208 ms |
49144 KB |
Output is correct |
60 |
Correct |
1236 ms |
49176 KB |
Output is correct |
61 |
Correct |
1402 ms |
85656 KB |
Output is correct |
62 |
Correct |
1230 ms |
78632 KB |
Output is correct |
63 |
Correct |
664 ms |
1792 KB |
Output is correct |
64 |
Correct |
940 ms |
2112 KB |
Output is correct |
65 |
Correct |
1132 ms |
47312 KB |
Output is correct |
66 |
Correct |
1474 ms |
40936 KB |
Output is correct |
67 |
Correct |
1048 ms |
1856 KB |
Output is correct |
68 |
Correct |
1000 ms |
2176 KB |
Output is correct |
69 |
Correct |
1788 ms |
83144 KB |
Output is correct |
70 |
Correct |
1564 ms |
68208 KB |
Output is correct |
71 |
Correct |
864 ms |
9128 KB |
Output is correct |
72 |
Correct |
925 ms |
2408 KB |
Output is correct |