#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
typedef pair <int, int> pii;
const int ID = 11;
const int DIST = 9;
namespace{
priority_queue <pii> Q;
vector <pii> G[2020];
vector <int> D;
bool chk[2020];
int v, c, t, _d;
int n, z;
void sendint(int x, int l)
{
x = min(x, (1 << l) - 1);
for(; l--; ){
SendA((x & (1 << l))? 1 : 0);
}
}
void check()
{
int p, d;
for(; !Q.empty(); Q.pop()){
tie(d, p) = Q.top(); d = -d;
if(!chk[p] && d == D[p]) break;
}
if(Q.empty()) return;
tie(d, p) = Q.top(); d = -d;
sendint(d - z, DIST);
}
void apply(int p, int d)
{
chk[p] = 1; D[p] = d; z = d;
for(pii &t: G[p]){
if(!chk[t.first] && D[t.first] > d + t.second){
D[t.first] = d + t.second;
Q.emplace(-d - t.second, t.first);
}
}
check();
}
void check(int d1)
{
int p2, d2;
tie(d2, p2) = Q.top(); d2 = -d2;
if(d1 < d2) _d = d1, t = 1;
else{
Q.pop();
sendint(p2, ID);
apply(p2, d2);
}
}
}
void InitA(int N, int A, vector <int> U, vector <int> V, vector<int> C)
{
n = N; D.resize(n, 0);
int i;
for(i=0; i<A; i++){
G[U[i]].emplace_back(V[i], C[i]);
G[V[i]].emplace_back(U[i], C[i]);
}
for(i=1; i<n; i++){
D[i] = 1e9;
}
for(i=0; i<n; i++){
Q.emplace(-D[i], i);
}
apply(0, 0);
}
void ReceiveA(bool x)
{
if(t == 0){
v = v << 1 | x; c ++;
if(c == DIST){
int d = z + v;
v = 0; c = 0;
check(d);
}
}
else{
v = v << 1 | x; c ++;
if(c == ID){
int p = v, d = _d;
v = 0; c = 0; t = 0;
apply(p, d);
}
}
}
vector <int> Answer() { return D; }
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
typedef pair <int, int> pii;
const int ID = 11;
const int DIST = 9;
namespace{
priority_queue <pii> Q;
vector <pii> G[2020];
vector <int> D;
bool chk[2020];
int v, c, t, _d;
int n, z;
void sendint(int x, int l)
{
x = min(x, (1 << l) - 1);
for(; l--; ){
SendB((x & (1 << l))? 1 : 0);
}
}
void check()
{
int p, d;
for(; !Q.empty(); Q.pop()){
tie(d, p) = Q.top(); d = -d;
if(!chk[p] && d == D[p]) break;
}
if(Q.empty()) return;
tie(d, p) = Q.top(); d = -d;
sendint(d - z, DIST);
}
void apply(int p, int d)
{
chk[p] = 1; D[p] = d; z = d;
for(pii &t: G[p]){
if(!chk[t.first] && D[t.first] > d + t.second){
D[t.first] = d + t.second;
Q.emplace(-d - t.second, t.first);
}
}
check();
}
void check(int d1)
{
int p2, d2;
tie(d2, p2) = Q.top(); d2 = -d2;
if(d1 <= d2) _d = d1, t = 1;
else{
Q.pop();
sendint(p2, ID);
apply(p2, d2);
}
}
}
void InitB(int N, int B, vector <int> S, vector<int> T, vector<int> C)
{
n = N; D.resize(n, 0);
int i;
for(i=0; i<B; i++){
G[S[i]].emplace_back(T[i], C[i]);
G[T[i]].emplace_back(S[i], C[i]);
}
for(i=1; i<n; i++){
D[i] = 1e9;
}
for(i=0; i<n; i++){
Q.emplace(-D[i], i);
}
apply(0, 0);
}
void ReceiveB(bool x)
{
if(t == 0){
v = v << 1 | x; c ++;
if(c == DIST){
int d = z + v;
v = 0; c = 0;
check(d);
}
}
else{
v = v << 1 | x; c ++;
if(c == ID){
int p = v, d = _d;
v = 0; c = 0; t = 0;
apply(p, d);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1182 ms |
2016 KB |
Output is correct |
2 |
Correct |
8 ms |
1248 KB |
Output is correct |
3 |
Correct |
1045 ms |
1576 KB |
Output is correct |
4 |
Correct |
1388 ms |
20184 KB |
Output is correct |
5 |
Correct |
56 ms |
1768 KB |
Output is correct |
6 |
Correct |
982 ms |
4376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1136 KB |
Output is correct |
2 |
Correct |
1232 ms |
1760 KB |
Output is correct |
3 |
Correct |
1088 ms |
1856 KB |
Output is correct |
4 |
Correct |
1740 ms |
54936 KB |
Output is correct |
5 |
Correct |
1386 ms |
48320 KB |
Output is correct |
6 |
Correct |
158 ms |
1504 KB |
Output is correct |
7 |
Correct |
1444 ms |
48576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1000 ms |
1992 KB |
Output is correct |
2 |
Correct |
6 ms |
992 KB |
Output is correct |
3 |
Correct |
940 ms |
1864 KB |
Output is correct |
4 |
Correct |
886 ms |
1984 KB |
Output is correct |
5 |
Correct |
1210 ms |
2008 KB |
Output is correct |
6 |
Correct |
914 ms |
1616 KB |
Output is correct |
7 |
Correct |
832 ms |
1808 KB |
Output is correct |
8 |
Correct |
956 ms |
1608 KB |
Output is correct |
9 |
Correct |
935 ms |
1816 KB |
Output is correct |
10 |
Correct |
1084 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
1760 KB |
Output is correct |
2 |
Correct |
571 ms |
1512 KB |
Output is correct |
3 |
Correct |
806 ms |
23760 KB |
Output is correct |
4 |
Correct |
606 ms |
1760 KB |
Output is correct |
5 |
Correct |
736 ms |
17416 KB |
Output is correct |
6 |
Correct |
294 ms |
1504 KB |
Output is correct |
7 |
Correct |
440 ms |
1472 KB |
Output is correct |
8 |
Correct |
462 ms |
1648 KB |
Output is correct |
9 |
Correct |
698 ms |
36024 KB |
Output is correct |
10 |
Correct |
790 ms |
35880 KB |
Output is correct |
11 |
Correct |
996 ms |
61072 KB |
Output is correct |
12 |
Correct |
1074 ms |
53576 KB |
Output is correct |
13 |
Correct |
424 ms |
1504 KB |
Output is correct |
14 |
Correct |
7 ms |
1248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
1760 KB |
Output is correct |
2 |
Correct |
571 ms |
1512 KB |
Output is correct |
3 |
Correct |
806 ms |
23760 KB |
Output is correct |
4 |
Correct |
606 ms |
1760 KB |
Output is correct |
5 |
Correct |
736 ms |
17416 KB |
Output is correct |
6 |
Correct |
294 ms |
1504 KB |
Output is correct |
7 |
Correct |
440 ms |
1472 KB |
Output is correct |
8 |
Correct |
462 ms |
1648 KB |
Output is correct |
9 |
Correct |
698 ms |
36024 KB |
Output is correct |
10 |
Correct |
790 ms |
35880 KB |
Output is correct |
11 |
Correct |
996 ms |
61072 KB |
Output is correct |
12 |
Correct |
1074 ms |
53576 KB |
Output is correct |
13 |
Correct |
424 ms |
1504 KB |
Output is correct |
14 |
Correct |
7 ms |
1248 KB |
Output is correct |
15 |
Correct |
556 ms |
1600 KB |
Output is correct |
16 |
Correct |
498 ms |
1376 KB |
Output is correct |
17 |
Correct |
504 ms |
1384 KB |
Output is correct |
18 |
Correct |
710 ms |
17616 KB |
Output is correct |
19 |
Correct |
506 ms |
1592 KB |
Output is correct |
20 |
Correct |
654 ms |
18320 KB |
Output is correct |
21 |
Correct |
448 ms |
1584 KB |
Output is correct |
22 |
Correct |
618 ms |
1856 KB |
Output is correct |
23 |
Correct |
974 ms |
43904 KB |
Output is correct |
24 |
Correct |
1032 ms |
43856 KB |
Output is correct |
25 |
Correct |
1326 ms |
74952 KB |
Output is correct |
26 |
Correct |
1137 ms |
64312 KB |
Output is correct |
27 |
Correct |
539 ms |
1800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
1760 KB |
Output is correct |
2 |
Correct |
571 ms |
1512 KB |
Output is correct |
3 |
Correct |
806 ms |
23760 KB |
Output is correct |
4 |
Correct |
606 ms |
1760 KB |
Output is correct |
5 |
Correct |
736 ms |
17416 KB |
Output is correct |
6 |
Correct |
294 ms |
1504 KB |
Output is correct |
7 |
Correct |
440 ms |
1472 KB |
Output is correct |
8 |
Correct |
462 ms |
1648 KB |
Output is correct |
9 |
Correct |
698 ms |
36024 KB |
Output is correct |
10 |
Correct |
790 ms |
35880 KB |
Output is correct |
11 |
Correct |
996 ms |
61072 KB |
Output is correct |
12 |
Correct |
1074 ms |
53576 KB |
Output is correct |
13 |
Correct |
424 ms |
1504 KB |
Output is correct |
14 |
Correct |
7 ms |
1248 KB |
Output is correct |
15 |
Correct |
556 ms |
1600 KB |
Output is correct |
16 |
Correct |
498 ms |
1376 KB |
Output is correct |
17 |
Correct |
504 ms |
1384 KB |
Output is correct |
18 |
Correct |
710 ms |
17616 KB |
Output is correct |
19 |
Correct |
506 ms |
1592 KB |
Output is correct |
20 |
Correct |
654 ms |
18320 KB |
Output is correct |
21 |
Correct |
448 ms |
1584 KB |
Output is correct |
22 |
Correct |
618 ms |
1856 KB |
Output is correct |
23 |
Correct |
974 ms |
43904 KB |
Output is correct |
24 |
Correct |
1032 ms |
43856 KB |
Output is correct |
25 |
Correct |
1326 ms |
74952 KB |
Output is correct |
26 |
Correct |
1137 ms |
64312 KB |
Output is correct |
27 |
Correct |
539 ms |
1800 KB |
Output is correct |
28 |
Correct |
816 ms |
1608 KB |
Output is correct |
29 |
Correct |
918 ms |
1576 KB |
Output is correct |
30 |
Correct |
1376 ms |
42112 KB |
Output is correct |
31 |
Correct |
736 ms |
1864 KB |
Output is correct |
32 |
Correct |
1128 ms |
37608 KB |
Output is correct |
33 |
Correct |
862 ms |
1936 KB |
Output is correct |
34 |
Correct |
748 ms |
2000 KB |
Output is correct |
35 |
Correct |
662 ms |
1824 KB |
Output is correct |
36 |
Correct |
1046 ms |
49280 KB |
Output is correct |
37 |
Correct |
1066 ms |
49184 KB |
Output is correct |
38 |
Correct |
1460 ms |
85584 KB |
Output is correct |
39 |
Correct |
1312 ms |
78504 KB |
Output is correct |
40 |
Correct |
736 ms |
1992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1182 ms |
2016 KB |
Output is correct |
2 |
Correct |
8 ms |
1248 KB |
Output is correct |
3 |
Correct |
1045 ms |
1576 KB |
Output is correct |
4 |
Correct |
1388 ms |
20184 KB |
Output is correct |
5 |
Correct |
56 ms |
1768 KB |
Output is correct |
6 |
Correct |
982 ms |
4376 KB |
Output is correct |
7 |
Correct |
4 ms |
1136 KB |
Output is correct |
8 |
Correct |
1232 ms |
1760 KB |
Output is correct |
9 |
Correct |
1088 ms |
1856 KB |
Output is correct |
10 |
Correct |
1740 ms |
54936 KB |
Output is correct |
11 |
Correct |
1386 ms |
48320 KB |
Output is correct |
12 |
Correct |
158 ms |
1504 KB |
Output is correct |
13 |
Correct |
1444 ms |
48576 KB |
Output is correct |
14 |
Correct |
1000 ms |
1992 KB |
Output is correct |
15 |
Correct |
6 ms |
992 KB |
Output is correct |
16 |
Correct |
940 ms |
1864 KB |
Output is correct |
17 |
Correct |
886 ms |
1984 KB |
Output is correct |
18 |
Correct |
1210 ms |
2008 KB |
Output is correct |
19 |
Correct |
914 ms |
1616 KB |
Output is correct |
20 |
Correct |
832 ms |
1808 KB |
Output is correct |
21 |
Correct |
956 ms |
1608 KB |
Output is correct |
22 |
Correct |
935 ms |
1816 KB |
Output is correct |
23 |
Correct |
1084 ms |
2040 KB |
Output is correct |
24 |
Correct |
438 ms |
1760 KB |
Output is correct |
25 |
Correct |
571 ms |
1512 KB |
Output is correct |
26 |
Correct |
806 ms |
23760 KB |
Output is correct |
27 |
Correct |
606 ms |
1760 KB |
Output is correct |
28 |
Correct |
736 ms |
17416 KB |
Output is correct |
29 |
Correct |
294 ms |
1504 KB |
Output is correct |
30 |
Correct |
440 ms |
1472 KB |
Output is correct |
31 |
Correct |
462 ms |
1648 KB |
Output is correct |
32 |
Correct |
698 ms |
36024 KB |
Output is correct |
33 |
Correct |
790 ms |
35880 KB |
Output is correct |
34 |
Correct |
996 ms |
61072 KB |
Output is correct |
35 |
Correct |
1074 ms |
53576 KB |
Output is correct |
36 |
Correct |
424 ms |
1504 KB |
Output is correct |
37 |
Correct |
7 ms |
1248 KB |
Output is correct |
38 |
Correct |
556 ms |
1600 KB |
Output is correct |
39 |
Correct |
498 ms |
1376 KB |
Output is correct |
40 |
Correct |
504 ms |
1384 KB |
Output is correct |
41 |
Correct |
710 ms |
17616 KB |
Output is correct |
42 |
Correct |
506 ms |
1592 KB |
Output is correct |
43 |
Correct |
654 ms |
18320 KB |
Output is correct |
44 |
Correct |
448 ms |
1584 KB |
Output is correct |
45 |
Correct |
618 ms |
1856 KB |
Output is correct |
46 |
Correct |
974 ms |
43904 KB |
Output is correct |
47 |
Correct |
1032 ms |
43856 KB |
Output is correct |
48 |
Correct |
1326 ms |
74952 KB |
Output is correct |
49 |
Correct |
1137 ms |
64312 KB |
Output is correct |
50 |
Correct |
539 ms |
1800 KB |
Output is correct |
51 |
Correct |
816 ms |
1608 KB |
Output is correct |
52 |
Correct |
918 ms |
1576 KB |
Output is correct |
53 |
Correct |
1376 ms |
42112 KB |
Output is correct |
54 |
Correct |
736 ms |
1864 KB |
Output is correct |
55 |
Correct |
1128 ms |
37608 KB |
Output is correct |
56 |
Correct |
862 ms |
1936 KB |
Output is correct |
57 |
Correct |
748 ms |
2000 KB |
Output is correct |
58 |
Correct |
662 ms |
1824 KB |
Output is correct |
59 |
Correct |
1046 ms |
49280 KB |
Output is correct |
60 |
Correct |
1066 ms |
49184 KB |
Output is correct |
61 |
Correct |
1460 ms |
85584 KB |
Output is correct |
62 |
Correct |
1312 ms |
78504 KB |
Output is correct |
63 |
Correct |
736 ms |
1992 KB |
Output is correct |
64 |
Correct |
1036 ms |
2072 KB |
Output is correct |
65 |
Correct |
1599 ms |
47072 KB |
Output is correct |
66 |
Correct |
1732 ms |
40928 KB |
Output is correct |
67 |
Correct |
1232 ms |
2144 KB |
Output is correct |
68 |
Correct |
1214 ms |
2016 KB |
Output is correct |
69 |
Correct |
1918 ms |
83552 KB |
Output is correct |
70 |
Correct |
1996 ms |
68176 KB |
Output is correct |
71 |
Correct |
1202 ms |
9120 KB |
Output is correct |
72 |
Correct |
776 ms |
2448 KB |
Output is correct |