#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
const int NA = 2001;
const int INFA = (int)1e9;
int nA;
vector <int> distA;
vector <pair <int, int> > vA[NA];
set <pair <int, int> > readyA;
int mx_distA = 0, cntA = 0, completeA = 0, waiting_forA;
vector <int> curA;
void addA(int node, int d){
completeA++;
mx_distA += d;
distA[node] = mx_distA;
for(auto &i : vA[node]){
if(distA[node] + i.second < distA[i.first]){
readyA.insert(make_pair(distA[node] + i.second, i.first));
}
}
}
pair <int, int> get_nextA(){
while(readyA.size() && distA[readyA.begin()->second] != INFA){
readyA.erase(readyA.begin());
}
if(readyA.size()){
return make_pair(readyA.begin()->first - mx_distA, readyA.begin()->second);
}
return make_pair(511, 511);
}
void SendA(){
if(completeA == nA) return;
waiting_forA = 9;
pair <int, int> f = get_nextA();
for(int i = 8 ; i >= 0 ; i--){
SendA((f.first >> i) & 1);
}
}
void InitA(int N, int A, vector <int> U, vector <int> V, vector <int> C){
nA = N;
for(int i = 0 ; i < A ; i++){
vA[U[i]].push_back(make_pair(V[i], C[i]));
vA[V[i]].push_back(make_pair(U[i], C[i]));
}
distA.resize(N, INFA);
distA[0] = 0;
addA(0, 0);
SendA();
}
void ReceiveA(bool x){
if(curA.size() == 0) curA.push_back(0);
curA.back() = curA.back() * 2 + x;
cntA++;
if(cntA == waiting_forA){
if(waiting_forA == 9){
auto g = get_nextA();
if(g.first <= curA.back()){
for(int i = 10 ; i >= 0 ; i--){
SendA((g.second >> i) & 1);
}
curA.clear();
cntA = 0;
addA(g.second, g.first);
SendA();
}
else{
curA.push_back(0);
cntA = 0;
waiting_forA = 11;
}
}
else{
assert(curA.size() == 2);
addA(curA[1], curA[0]);
SendA();
curA.clear();
cntA = 0;
}
}
}
vector <int> Answer(){
return distA;
}
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
const int NB = 2001;
const int INFB = (int)1e9;
int nB;
vector <int> distB;
vector <pair <int, int> > vB[NB];
set <pair <int, int> > readyB;
int mx_distB = 0, cntB = 0, waiting_forB;
vector <int> curB;
void addB(int node, int d){
mx_distB += d;
distB[node] = mx_distB;
for(auto &i : vB[node]){
if(distB[node] + i.second < distB[i.first]){
readyB.insert(make_pair(distB[node] + i.second, i.first));
}
}
}
pair <int, int> get_nextB(){
while(readyB.size() && distB[readyB.begin()->second] != INFB){
readyB.erase(readyB.begin());
}
if(readyB.size()){
return make_pair(readyB.begin()->first - mx_distB, readyB.begin()->second);
}
return make_pair(511, 511);
}
void InitB(int N, int B, vector <int> S, vector <int> T, vector <int> D){
nB = N;
for(int i = 0 ; i < B ; i++){
vB[S[i]].push_back(make_pair(T[i], D[i]));
vB[T[i]].push_back(make_pair(S[i], D[i]));
}
distB.resize(N, INFB);
distB[0] = 0;
addB(0, 0);
waiting_forB = 9;
}
void ReceiveB(bool y){
if(curB.size() == 0) curB.push_back(0);
curB.back() = 2 * curB.back() + y;
cntB++;
if(cntB == waiting_forB){
if(waiting_forB == 9){
auto g = get_nextB();
if(g.first < curB.back()){
for(int i = 8 ; i >= 0 ; i--){
SendB((g.first >> i) & 1);
}
for(int i = 10 ; i >= 0 ; i--){
SendB((g.second >> i) & 1);
}
addB(g.second, g.first);
curB.clear();
cntB = 0;
waiting_forB = 9;
}
else{
for(int i = 8 ; i >= 0 ; i--){
SendB(1);
}
waiting_forB = 11;
curB.push_back(0);
cntB = 0;
}
}
else{
assert(curB.size() == 2);
addB(curB[1], curB[0]);
curB.clear();
cntB = 0;
waiting_forB = 9;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
599 ms |
772 KB |
Output is correct |
2 |
Correct |
2 ms |
644 KB |
Output is correct |
3 |
Correct |
533 ms |
780 KB |
Output is correct |
4 |
Correct |
830 ms |
10092 KB |
Output is correct |
5 |
Correct |
31 ms |
924 KB |
Output is correct |
6 |
Correct |
622 ms |
3020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
640 KB |
Output is correct |
2 |
Correct |
512 ms |
732 KB |
Output is correct |
3 |
Correct |
544 ms |
792 KB |
Output is correct |
4 |
Correct |
987 ms |
27688 KB |
Output is correct |
5 |
Correct |
1172 ms |
33788 KB |
Output is correct |
6 |
Correct |
157 ms |
832 KB |
Output is correct |
7 |
Correct |
1308 ms |
33944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
509 ms |
720 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
690 ms |
648 KB |
Output is correct |
4 |
Correct |
548 ms |
736 KB |
Output is correct |
5 |
Correct |
506 ms |
732 KB |
Output is correct |
6 |
Correct |
615 ms |
728 KB |
Output is correct |
7 |
Correct |
528 ms |
724 KB |
Output is correct |
8 |
Correct |
536 ms |
660 KB |
Output is correct |
9 |
Correct |
615 ms |
804 KB |
Output is correct |
10 |
Correct |
545 ms |
772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
668 KB |
Output is correct |
2 |
Correct |
312 ms |
600 KB |
Output is correct |
3 |
Correct |
448 ms |
13316 KB |
Output is correct |
4 |
Correct |
305 ms |
664 KB |
Output is correct |
5 |
Correct |
483 ms |
10076 KB |
Output is correct |
6 |
Correct |
263 ms |
684 KB |
Output is correct |
7 |
Correct |
253 ms |
716 KB |
Output is correct |
8 |
Correct |
266 ms |
716 KB |
Output is correct |
9 |
Correct |
689 ms |
23952 KB |
Output is correct |
10 |
Correct |
676 ms |
23940 KB |
Output is correct |
11 |
Correct |
1218 ms |
47244 KB |
Output is correct |
12 |
Correct |
964 ms |
40868 KB |
Output is correct |
13 |
Correct |
271 ms |
840 KB |
Output is correct |
14 |
Correct |
2 ms |
644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
668 KB |
Output is correct |
2 |
Correct |
312 ms |
600 KB |
Output is correct |
3 |
Correct |
448 ms |
13316 KB |
Output is correct |
4 |
Correct |
305 ms |
664 KB |
Output is correct |
5 |
Correct |
483 ms |
10076 KB |
Output is correct |
6 |
Correct |
263 ms |
684 KB |
Output is correct |
7 |
Correct |
253 ms |
716 KB |
Output is correct |
8 |
Correct |
266 ms |
716 KB |
Output is correct |
9 |
Correct |
689 ms |
23952 KB |
Output is correct |
10 |
Correct |
676 ms |
23940 KB |
Output is correct |
11 |
Correct |
1218 ms |
47244 KB |
Output is correct |
12 |
Correct |
964 ms |
40868 KB |
Output is correct |
13 |
Correct |
271 ms |
840 KB |
Output is correct |
14 |
Correct |
2 ms |
644 KB |
Output is correct |
15 |
Correct |
276 ms |
676 KB |
Output is correct |
16 |
Correct |
309 ms |
704 KB |
Output is correct |
17 |
Correct |
307 ms |
640 KB |
Output is correct |
18 |
Correct |
544 ms |
10096 KB |
Output is correct |
19 |
Correct |
379 ms |
640 KB |
Output is correct |
20 |
Correct |
499 ms |
10360 KB |
Output is correct |
21 |
Correct |
348 ms |
640 KB |
Output is correct |
22 |
Correct |
406 ms |
640 KB |
Output is correct |
23 |
Correct |
830 ms |
29304 KB |
Output is correct |
24 |
Correct |
951 ms |
29308 KB |
Output is correct |
25 |
Correct |
1584 ms |
57828 KB |
Output is correct |
26 |
Correct |
1285 ms |
48872 KB |
Output is correct |
27 |
Correct |
281 ms |
900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
272 ms |
668 KB |
Output is correct |
2 |
Correct |
312 ms |
600 KB |
Output is correct |
3 |
Correct |
448 ms |
13316 KB |
Output is correct |
4 |
Correct |
305 ms |
664 KB |
Output is correct |
5 |
Correct |
483 ms |
10076 KB |
Output is correct |
6 |
Correct |
263 ms |
684 KB |
Output is correct |
7 |
Correct |
253 ms |
716 KB |
Output is correct |
8 |
Correct |
266 ms |
716 KB |
Output is correct |
9 |
Correct |
689 ms |
23952 KB |
Output is correct |
10 |
Correct |
676 ms |
23940 KB |
Output is correct |
11 |
Correct |
1218 ms |
47244 KB |
Output is correct |
12 |
Correct |
964 ms |
40868 KB |
Output is correct |
13 |
Correct |
271 ms |
840 KB |
Output is correct |
14 |
Correct |
2 ms |
644 KB |
Output is correct |
15 |
Correct |
276 ms |
676 KB |
Output is correct |
16 |
Correct |
309 ms |
704 KB |
Output is correct |
17 |
Correct |
307 ms |
640 KB |
Output is correct |
18 |
Correct |
544 ms |
10096 KB |
Output is correct |
19 |
Correct |
379 ms |
640 KB |
Output is correct |
20 |
Correct |
499 ms |
10360 KB |
Output is correct |
21 |
Correct |
348 ms |
640 KB |
Output is correct |
22 |
Correct |
406 ms |
640 KB |
Output is correct |
23 |
Correct |
830 ms |
29304 KB |
Output is correct |
24 |
Correct |
951 ms |
29308 KB |
Output is correct |
25 |
Correct |
1584 ms |
57828 KB |
Output is correct |
26 |
Correct |
1285 ms |
48872 KB |
Output is correct |
27 |
Correct |
281 ms |
900 KB |
Output is correct |
28 |
Correct |
472 ms |
692 KB |
Output is correct |
29 |
Correct |
399 ms |
648 KB |
Output is correct |
30 |
Correct |
898 ms |
24064 KB |
Output is correct |
31 |
Correct |
407 ms |
644 KB |
Output is correct |
32 |
Correct |
741 ms |
21100 KB |
Output is correct |
33 |
Correct |
478 ms |
720 KB |
Output is correct |
34 |
Correct |
238 ms |
748 KB |
Output is correct |
35 |
Correct |
411 ms |
756 KB |
Output is correct |
36 |
Correct |
954 ms |
33084 KB |
Output is correct |
37 |
Correct |
1031 ms |
33056 KB |
Output is correct |
38 |
Correct |
1797 ms |
65688 KB |
Output is correct |
39 |
Correct |
1570 ms |
59096 KB |
Output is correct |
40 |
Correct |
454 ms |
1088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
599 ms |
772 KB |
Output is correct |
2 |
Correct |
2 ms |
644 KB |
Output is correct |
3 |
Correct |
533 ms |
780 KB |
Output is correct |
4 |
Correct |
830 ms |
10092 KB |
Output is correct |
5 |
Correct |
31 ms |
924 KB |
Output is correct |
6 |
Correct |
622 ms |
3020 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
512 ms |
732 KB |
Output is correct |
9 |
Correct |
544 ms |
792 KB |
Output is correct |
10 |
Correct |
987 ms |
27688 KB |
Output is correct |
11 |
Correct |
1172 ms |
33788 KB |
Output is correct |
12 |
Correct |
157 ms |
832 KB |
Output is correct |
13 |
Correct |
1308 ms |
33944 KB |
Output is correct |
14 |
Correct |
509 ms |
720 KB |
Output is correct |
15 |
Correct |
2 ms |
640 KB |
Output is correct |
16 |
Correct |
690 ms |
648 KB |
Output is correct |
17 |
Correct |
548 ms |
736 KB |
Output is correct |
18 |
Correct |
506 ms |
732 KB |
Output is correct |
19 |
Correct |
615 ms |
728 KB |
Output is correct |
20 |
Correct |
528 ms |
724 KB |
Output is correct |
21 |
Correct |
536 ms |
660 KB |
Output is correct |
22 |
Correct |
615 ms |
804 KB |
Output is correct |
23 |
Correct |
545 ms |
772 KB |
Output is correct |
24 |
Correct |
272 ms |
668 KB |
Output is correct |
25 |
Correct |
312 ms |
600 KB |
Output is correct |
26 |
Correct |
448 ms |
13316 KB |
Output is correct |
27 |
Correct |
305 ms |
664 KB |
Output is correct |
28 |
Correct |
483 ms |
10076 KB |
Output is correct |
29 |
Correct |
263 ms |
684 KB |
Output is correct |
30 |
Correct |
253 ms |
716 KB |
Output is correct |
31 |
Correct |
266 ms |
716 KB |
Output is correct |
32 |
Correct |
689 ms |
23952 KB |
Output is correct |
33 |
Correct |
676 ms |
23940 KB |
Output is correct |
34 |
Correct |
1218 ms |
47244 KB |
Output is correct |
35 |
Correct |
964 ms |
40868 KB |
Output is correct |
36 |
Correct |
271 ms |
840 KB |
Output is correct |
37 |
Correct |
2 ms |
644 KB |
Output is correct |
38 |
Correct |
276 ms |
676 KB |
Output is correct |
39 |
Correct |
309 ms |
704 KB |
Output is correct |
40 |
Correct |
307 ms |
640 KB |
Output is correct |
41 |
Correct |
544 ms |
10096 KB |
Output is correct |
42 |
Correct |
379 ms |
640 KB |
Output is correct |
43 |
Correct |
499 ms |
10360 KB |
Output is correct |
44 |
Correct |
348 ms |
640 KB |
Output is correct |
45 |
Correct |
406 ms |
640 KB |
Output is correct |
46 |
Correct |
830 ms |
29304 KB |
Output is correct |
47 |
Correct |
951 ms |
29308 KB |
Output is correct |
48 |
Correct |
1584 ms |
57828 KB |
Output is correct |
49 |
Correct |
1285 ms |
48872 KB |
Output is correct |
50 |
Correct |
281 ms |
900 KB |
Output is correct |
51 |
Correct |
472 ms |
692 KB |
Output is correct |
52 |
Correct |
399 ms |
648 KB |
Output is correct |
53 |
Correct |
898 ms |
24064 KB |
Output is correct |
54 |
Correct |
407 ms |
644 KB |
Output is correct |
55 |
Correct |
741 ms |
21100 KB |
Output is correct |
56 |
Correct |
478 ms |
720 KB |
Output is correct |
57 |
Correct |
238 ms |
748 KB |
Output is correct |
58 |
Correct |
411 ms |
756 KB |
Output is correct |
59 |
Correct |
954 ms |
33084 KB |
Output is correct |
60 |
Correct |
1031 ms |
33056 KB |
Output is correct |
61 |
Correct |
1797 ms |
65688 KB |
Output is correct |
62 |
Correct |
1570 ms |
59096 KB |
Output is correct |
63 |
Correct |
454 ms |
1088 KB |
Output is correct |
64 |
Correct |
640 ms |
944 KB |
Output is correct |
65 |
Correct |
978 ms |
26492 KB |
Output is correct |
66 |
Correct |
1092 ms |
23252 KB |
Output is correct |
67 |
Correct |
513 ms |
924 KB |
Output is correct |
68 |
Correct |
661 ms |
924 KB |
Output is correct |
69 |
Correct |
2020 ms |
67012 KB |
Output is correct |
70 |
Correct |
1927 ms |
59472 KB |
Output is correct |
71 |
Correct |
653 ms |
8160 KB |
Output is correct |
72 |
Correct |
686 ms |
1540 KB |
Output is correct |