#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, f = 1234567890, b;
int n, z, m;
bool turn() { b = (b + 1) % 30; return (f & (1 << b)) != 0; }
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(p, ID);
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);
}
}
if(turn()){
m = 1; check();
}
else m = 2;
}
void check(int p1, int d1)
{
int p, d, p2, d2;
for(; !Q.empty(); Q.pop()){
tie(d2, p2) = Q.top(); d2 = -d2;
if(!chk[p2] && D[p2] == d2) break;
}
tie(d2, p2) = Q.top(); d2 = -d2;
if(d1 < d2){
p = p1, d = d1;
SendA(0);
}
else{
p = p2, d = d2; Q.pop();
SendA(1);
sendint(p, ID);
sendint(d - z, DIST);
}
apply(p, d);
}
}
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(m == 1){
if(t == 0){
if(!x){
int d, p;
tie(d, p) = Q.top();
d = -d; Q.pop();
apply(p, d);
}
else t = 1;
}
else{
v = v << 1 | x; c ++;
if(c == ID + DIST){
int p = v >> DIST;
int d = z + (v & ((1 << DIST) - 1));
v = 0; c = 0; t = 0;
apply(p, d);
}
}
}
else{
v = v << 1 | x; c ++;
if(c == ID + DIST){
int p = v >> DIST;
int d = z + (v & ((1 << DIST) - 1));
v = 0; c = 0;
check(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, f = 1234567890, b;
int n, z, m;
bool turn() { b = (b + 1) % 30; return (f & (1 << b)) != 0; }
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(p, ID);
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);
}
}
if(!turn()){
m = 1; check();
}
else m = 2;
}
void check(int p1, int d1)
{
int p, d, p2, d2;
for(; !Q.empty(); Q.pop()){
tie(d2, p2) = Q.top(); d2 = -d2;
if(!chk[p2] && D[p2] == d2) break;
}
tie(d2, p2) = Q.top(); d2 = -d2;
if(d1 < d2){
p = p1, d = d1;
SendB(0);
}
else{
p = p2, d = d2; Q.pop();
SendB(1);
sendint(p, ID);
sendint(d - z, DIST);
}
apply(p, d);
}
}
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 y)
{
if(m == 1){
if(t == 0){
if(!y){
int d, p;
tie(d, p) = Q.top();
d = -d; Q.pop();
apply(p, d);
}
else t = 1;
}
else{
v = v << 1 | y; c ++;
if(c == ID + DIST){
int p = v >> DIST;
int d = z + (v & ((1 << DIST) - 1));
v = 0; c = 0; t = 0;
apply(p, d);
}
}
}
else{
v = v << 1 | y; c ++;
if(c == ID + DIST){
int p = v >> DIST;
int d = z + (v & ((1 << DIST) - 1));
v = 0; c = 0;
check(p, d);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
978 ms |
1760 KB |
Output is correct |
2 |
Correct |
6 ms |
1256 KB |
Output is correct |
3 |
Correct |
1002 ms |
2024 KB |
Output is correct |
4 |
Correct |
1268 ms |
20464 KB |
Output is correct |
5 |
Correct |
36 ms |
1416 KB |
Output is correct |
6 |
Correct |
860 ms |
4520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1392 KB |
Output is correct |
2 |
Incorrect |
545 ms |
732 KB |
Wrong Answer [2] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
399 ms |
880 KB |
Wrong Answer [2] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
592 ms |
1376 KB |
Output is correct |
2 |
Correct |
444 ms |
1512 KB |
Output is correct |
3 |
Correct |
882 ms |
23696 KB |
Output is correct |
4 |
Correct |
328 ms |
1600 KB |
Output is correct |
5 |
Correct |
803 ms |
17248 KB |
Output is correct |
6 |
Correct |
572 ms |
1592 KB |
Output is correct |
7 |
Correct |
473 ms |
1408 KB |
Output is correct |
8 |
Correct |
572 ms |
1736 KB |
Output is correct |
9 |
Correct |
962 ms |
35776 KB |
Output is correct |
10 |
Correct |
635 ms |
36008 KB |
Output is correct |
11 |
Correct |
1238 ms |
61344 KB |
Output is correct |
12 |
Correct |
1260 ms |
53880 KB |
Output is correct |
13 |
Correct |
536 ms |
1608 KB |
Output is correct |
14 |
Correct |
8 ms |
1248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
592 ms |
1376 KB |
Output is correct |
2 |
Correct |
444 ms |
1512 KB |
Output is correct |
3 |
Correct |
882 ms |
23696 KB |
Output is correct |
4 |
Correct |
328 ms |
1600 KB |
Output is correct |
5 |
Correct |
803 ms |
17248 KB |
Output is correct |
6 |
Correct |
572 ms |
1592 KB |
Output is correct |
7 |
Correct |
473 ms |
1408 KB |
Output is correct |
8 |
Correct |
572 ms |
1736 KB |
Output is correct |
9 |
Correct |
962 ms |
35776 KB |
Output is correct |
10 |
Correct |
635 ms |
36008 KB |
Output is correct |
11 |
Correct |
1238 ms |
61344 KB |
Output is correct |
12 |
Correct |
1260 ms |
53880 KB |
Output is correct |
13 |
Correct |
536 ms |
1608 KB |
Output is correct |
14 |
Correct |
8 ms |
1248 KB |
Output is correct |
15 |
Correct |
614 ms |
1528 KB |
Output is correct |
16 |
Correct |
752 ms |
1832 KB |
Output is correct |
17 |
Correct |
713 ms |
1504 KB |
Output is correct |
18 |
Correct |
984 ms |
17472 KB |
Output is correct |
19 |
Correct |
635 ms |
1584 KB |
Output is correct |
20 |
Correct |
866 ms |
18208 KB |
Output is correct |
21 |
Correct |
680 ms |
1632 KB |
Output is correct |
22 |
Correct |
734 ms |
1688 KB |
Output is correct |
23 |
Correct |
1206 ms |
43944 KB |
Output is correct |
24 |
Correct |
1066 ms |
44000 KB |
Output is correct |
25 |
Correct |
1816 ms |
74992 KB |
Output is correct |
26 |
Correct |
1162 ms |
64320 KB |
Output is correct |
27 |
Correct |
626 ms |
2024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
592 ms |
1376 KB |
Output is correct |
2 |
Correct |
444 ms |
1512 KB |
Output is correct |
3 |
Correct |
882 ms |
23696 KB |
Output is correct |
4 |
Correct |
328 ms |
1600 KB |
Output is correct |
5 |
Correct |
803 ms |
17248 KB |
Output is correct |
6 |
Correct |
572 ms |
1592 KB |
Output is correct |
7 |
Correct |
473 ms |
1408 KB |
Output is correct |
8 |
Correct |
572 ms |
1736 KB |
Output is correct |
9 |
Correct |
962 ms |
35776 KB |
Output is correct |
10 |
Correct |
635 ms |
36008 KB |
Output is correct |
11 |
Correct |
1238 ms |
61344 KB |
Output is correct |
12 |
Correct |
1260 ms |
53880 KB |
Output is correct |
13 |
Correct |
536 ms |
1608 KB |
Output is correct |
14 |
Correct |
8 ms |
1248 KB |
Output is correct |
15 |
Correct |
614 ms |
1528 KB |
Output is correct |
16 |
Correct |
752 ms |
1832 KB |
Output is correct |
17 |
Correct |
713 ms |
1504 KB |
Output is correct |
18 |
Correct |
984 ms |
17472 KB |
Output is correct |
19 |
Correct |
635 ms |
1584 KB |
Output is correct |
20 |
Correct |
866 ms |
18208 KB |
Output is correct |
21 |
Correct |
680 ms |
1632 KB |
Output is correct |
22 |
Correct |
734 ms |
1688 KB |
Output is correct |
23 |
Correct |
1206 ms |
43944 KB |
Output is correct |
24 |
Correct |
1066 ms |
44000 KB |
Output is correct |
25 |
Correct |
1816 ms |
74992 KB |
Output is correct |
26 |
Correct |
1162 ms |
64320 KB |
Output is correct |
27 |
Correct |
626 ms |
2024 KB |
Output is correct |
28 |
Correct |
800 ms |
1560 KB |
Output is correct |
29 |
Correct |
622 ms |
1760 KB |
Output is correct |
30 |
Correct |
1300 ms |
42160 KB |
Output is correct |
31 |
Correct |
498 ms |
1768 KB |
Output is correct |
32 |
Correct |
1364 ms |
37488 KB |
Output is correct |
33 |
Correct |
834 ms |
1944 KB |
Output is correct |
34 |
Correct |
719 ms |
1816 KB |
Output is correct |
35 |
Correct |
762 ms |
1736 KB |
Output is correct |
36 |
Correct |
1366 ms |
49320 KB |
Output is correct |
37 |
Correct |
1012 ms |
49152 KB |
Output is correct |
38 |
Correct |
1952 ms |
85384 KB |
Output is correct |
39 |
Correct |
1770 ms |
78584 KB |
Output is correct |
40 |
Correct |
752 ms |
2408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
978 ms |
1760 KB |
Output is correct |
2 |
Correct |
6 ms |
1256 KB |
Output is correct |
3 |
Correct |
1002 ms |
2024 KB |
Output is correct |
4 |
Correct |
1268 ms |
20464 KB |
Output is correct |
5 |
Correct |
36 ms |
1416 KB |
Output is correct |
6 |
Correct |
860 ms |
4520 KB |
Output is correct |
7 |
Correct |
2 ms |
1392 KB |
Output is correct |
8 |
Incorrect |
545 ms |
732 KB |
Wrong Answer [2] |
9 |
Halted |
0 ms |
0 KB |
- |