#include<bits/stdc++.h>
#include "Azer.h"
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef int64_t lld;
typedef pair<int, int> pii;
namespace {
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<vector<pii>> G;
vector<int> dist;
const int POINT = 11, WEIGHT = 9;
int pending = 0;
bool pendF = false; // true: POINT, false: WEIGHT
void pend(int len){
assert(pending == 0);
pendF = (len == POINT);
pending = len;
//cerr << "Azer: pend" << endl;
}
void send(int x, int len){
for(int i = len-1; i >= 0; i--)
SendA((x>>i)&1);
//cerr << "Azer: send " << x << endl;
}
int cur = 0;
void bfs(pii p){
assert(!dist[p.ss]);
dist[p.ss] = p.ff;
//cerr << "BFS" << p.ss << " " << p.ff << endl;
for(auto i: G[p.ss]){
if(dist[i.ss])
continue;
pq.push({i.ff+p.ff, i.ss});
}
while(!pq.empty() && dist[pq.top().ss])pq.pop();
if(pq.empty())send(505, WEIGHT);
else send(pq.top().ff-cur, WEIGHT);
pend(WEIGHT);
}
void receiveWeight(int w){
if(!pq.empty() && w + cur > pq.top().ff){
cur = pq.top().ff;
assert(!dist[pq.top().ss]);
send(pq.top().ss, POINT);
auto a = pq.top(); pq.pop();
bfs(a);
}else{
if(w == 505)return;
cur += w;
pend(POINT);
}
}
void receivePoint(int x){
bfs({cur, x});
}
};
void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
G.resize(N);
dist.resize(N);
for(int i = 0; i < A; i++){
G[U[i]].pb({C[i], V[i]});
G[V[i]].pb({C[i], U[i]});
}
bfs({1, 0});
}
void ReceiveA(bool x){
static int cc = 0;
cc = (cc<<1)+x;
if(--pending)return;
//cerr << "Azer: rece " << cc << endl;
pendF?receivePoint(cc):receiveWeight(cc);
cc = 0;
}
vector<int> Answer(){
for(auto& i: dist)i--;
return dist;
}
#include<bits/stdc++.h>
#include "Baijan.h"
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef int64_t lld;
typedef pair<int, int> pii;
namespace {
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<vector<pii>> G;
vector<int> dist;
const int POINT = 11, WEIGHT = 9;
int pending = 0;
bool pendF = false; // true: POINT, false: WEIGHT
void pend(int len){
assert(pending == 0);
pendF = (len == POINT);
pending = len;
//cerr << "Baij: pend" << endl;
}
void send(int x, int len){
for(int i = len-1; i >= 0; i--)
SendB((x>>i)&1);
//cerr << "Baij: send " << x << endl;
}
int cur = 0;
void bfs(pii p){
assert(!dist[p.ss]);
dist[p.ss] = p.ff;
for(auto i: G[p.ss]){
if(dist[i.ss])
continue;
pq.push({i.ff+p.ff, i.ss});
}
while(!pq.empty() && dist[pq.top().ss])pq.pop();
if(pq.empty())send(505, WEIGHT);
else send(pq.top().ff-cur, WEIGHT);
pend(WEIGHT);
}
void receiveWeight(int w){
if(!pq.empty() && w + cur >= pq.top().ff){
cur = pq.top().ff;
assert(!dist[pq.top().ss]);
send(pq.top().ss, POINT);
auto a = pq.top(); pq.pop();
bfs(a);
}else{
if(w == 505)return;
cur += w;
pend(POINT);
}
}
void receivePoint(int x){
bfs({cur, x});
}
};
void InitB(int N, int B, vector<int> U, vector<int> V, vector<int> C) {
G.resize(N);
dist.resize(N);
for(int i = 0; i < B; i++){
G[U[i]].pb({C[i], V[i]});
G[V[i]].pb({C[i], U[i]});
}
bfs({1, 0});
}
void ReceiveB(bool x){
static int cc = 0;
cc = (cc<<1)+x;
if(--pending)return;
//cerr << "Baij: rece " << cc << endl;
pendF?receivePoint(cc):receiveWeight(cc);
cc = 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
928 ms |
1568 KB |
Output is correct |
2 |
Correct |
18 ms |
1248 KB |
Output is correct |
3 |
Correct |
926 ms |
1512 KB |
Output is correct |
4 |
Correct |
1200 ms |
20016 KB |
Output is correct |
5 |
Correct |
73 ms |
2016 KB |
Output is correct |
6 |
Correct |
1066 ms |
4616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
992 KB |
Output is correct |
2 |
Correct |
1012 ms |
1512 KB |
Output is correct |
3 |
Correct |
996 ms |
2016 KB |
Output is correct |
4 |
Correct |
1604 ms |
55520 KB |
Output is correct |
5 |
Correct |
1634 ms |
48696 KB |
Output is correct |
6 |
Correct |
242 ms |
1248 KB |
Output is correct |
7 |
Correct |
1626 ms |
48888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
788 ms |
1632 KB |
Output is correct |
2 |
Correct |
18 ms |
1248 KB |
Output is correct |
3 |
Correct |
962 ms |
1504 KB |
Output is correct |
4 |
Correct |
1070 ms |
2016 KB |
Output is correct |
5 |
Correct |
944 ms |
1504 KB |
Output is correct |
6 |
Correct |
1080 ms |
1760 KB |
Output is correct |
7 |
Correct |
986 ms |
1760 KB |
Output is correct |
8 |
Correct |
1020 ms |
1744 KB |
Output is correct |
9 |
Correct |
956 ms |
1328 KB |
Output is correct |
10 |
Correct |
978 ms |
1504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
366 ms |
1272 KB |
Output is correct |
2 |
Correct |
468 ms |
1248 KB |
Output is correct |
3 |
Correct |
754 ms |
23800 KB |
Output is correct |
4 |
Correct |
470 ms |
1760 KB |
Output is correct |
5 |
Correct |
676 ms |
17464 KB |
Output is correct |
6 |
Correct |
458 ms |
1504 KB |
Output is correct |
7 |
Correct |
450 ms |
1768 KB |
Output is correct |
8 |
Correct |
478 ms |
1760 KB |
Output is correct |
9 |
Correct |
994 ms |
38824 KB |
Output is correct |
10 |
Correct |
948 ms |
38576 KB |
Output is correct |
11 |
Correct |
1478 ms |
72816 KB |
Output is correct |
12 |
Correct |
1226 ms |
67256 KB |
Output is correct |
13 |
Correct |
468 ms |
1760 KB |
Output is correct |
14 |
Correct |
18 ms |
1256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
366 ms |
1272 KB |
Output is correct |
2 |
Correct |
468 ms |
1248 KB |
Output is correct |
3 |
Correct |
754 ms |
23800 KB |
Output is correct |
4 |
Correct |
470 ms |
1760 KB |
Output is correct |
5 |
Correct |
676 ms |
17464 KB |
Output is correct |
6 |
Correct |
458 ms |
1504 KB |
Output is correct |
7 |
Correct |
450 ms |
1768 KB |
Output is correct |
8 |
Correct |
478 ms |
1760 KB |
Output is correct |
9 |
Correct |
994 ms |
38824 KB |
Output is correct |
10 |
Correct |
948 ms |
38576 KB |
Output is correct |
11 |
Correct |
1478 ms |
72816 KB |
Output is correct |
12 |
Correct |
1226 ms |
67256 KB |
Output is correct |
13 |
Correct |
468 ms |
1760 KB |
Output is correct |
14 |
Correct |
18 ms |
1256 KB |
Output is correct |
15 |
Correct |
580 ms |
1248 KB |
Output is correct |
16 |
Correct |
594 ms |
1504 KB |
Output is correct |
17 |
Correct |
602 ms |
1504 KB |
Output is correct |
18 |
Correct |
848 ms |
17672 KB |
Output is correct |
19 |
Correct |
520 ms |
1760 KB |
Output is correct |
20 |
Correct |
888 ms |
17992 KB |
Output is correct |
21 |
Correct |
592 ms |
1768 KB |
Output is correct |
22 |
Correct |
626 ms |
1760 KB |
Output is correct |
23 |
Correct |
1172 ms |
44784 KB |
Output is correct |
24 |
Correct |
1174 ms |
44528 KB |
Output is correct |
25 |
Correct |
1832 ms |
87080 KB |
Output is correct |
26 |
Correct |
1508 ms |
76960 KB |
Output is correct |
27 |
Correct |
530 ms |
1760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
366 ms |
1272 KB |
Output is correct |
2 |
Correct |
468 ms |
1248 KB |
Output is correct |
3 |
Correct |
754 ms |
23800 KB |
Output is correct |
4 |
Correct |
470 ms |
1760 KB |
Output is correct |
5 |
Correct |
676 ms |
17464 KB |
Output is correct |
6 |
Correct |
458 ms |
1504 KB |
Output is correct |
7 |
Correct |
450 ms |
1768 KB |
Output is correct |
8 |
Correct |
478 ms |
1760 KB |
Output is correct |
9 |
Correct |
994 ms |
38824 KB |
Output is correct |
10 |
Correct |
948 ms |
38576 KB |
Output is correct |
11 |
Correct |
1478 ms |
72816 KB |
Output is correct |
12 |
Correct |
1226 ms |
67256 KB |
Output is correct |
13 |
Correct |
468 ms |
1760 KB |
Output is correct |
14 |
Correct |
18 ms |
1256 KB |
Output is correct |
15 |
Correct |
580 ms |
1248 KB |
Output is correct |
16 |
Correct |
594 ms |
1504 KB |
Output is correct |
17 |
Correct |
602 ms |
1504 KB |
Output is correct |
18 |
Correct |
848 ms |
17672 KB |
Output is correct |
19 |
Correct |
520 ms |
1760 KB |
Output is correct |
20 |
Correct |
888 ms |
17992 KB |
Output is correct |
21 |
Correct |
592 ms |
1768 KB |
Output is correct |
22 |
Correct |
626 ms |
1760 KB |
Output is correct |
23 |
Correct |
1172 ms |
44784 KB |
Output is correct |
24 |
Correct |
1174 ms |
44528 KB |
Output is correct |
25 |
Correct |
1832 ms |
87080 KB |
Output is correct |
26 |
Correct |
1508 ms |
76960 KB |
Output is correct |
27 |
Correct |
530 ms |
1760 KB |
Output is correct |
28 |
Correct |
716 ms |
1568 KB |
Output is correct |
29 |
Correct |
702 ms |
1256 KB |
Output is correct |
30 |
Correct |
1346 ms |
41952 KB |
Output is correct |
31 |
Correct |
724 ms |
1584 KB |
Output is correct |
32 |
Correct |
1162 ms |
37504 KB |
Output is correct |
33 |
Correct |
762 ms |
1760 KB |
Output is correct |
34 |
Correct |
782 ms |
1760 KB |
Output is correct |
35 |
Correct |
768 ms |
1760 KB |
Output is correct |
36 |
Correct |
1344 ms |
49904 KB |
Output is correct |
37 |
Correct |
1320 ms |
49648 KB |
Output is correct |
38 |
Correct |
2028 ms |
97344 KB |
Output is correct |
39 |
Correct |
1712 ms |
89704 KB |
Output is correct |
40 |
Correct |
742 ms |
1752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
928 ms |
1568 KB |
Output is correct |
2 |
Correct |
18 ms |
1248 KB |
Output is correct |
3 |
Correct |
926 ms |
1512 KB |
Output is correct |
4 |
Correct |
1200 ms |
20016 KB |
Output is correct |
5 |
Correct |
73 ms |
2016 KB |
Output is correct |
6 |
Correct |
1066 ms |
4616 KB |
Output is correct |
7 |
Correct |
18 ms |
992 KB |
Output is correct |
8 |
Correct |
1012 ms |
1512 KB |
Output is correct |
9 |
Correct |
996 ms |
2016 KB |
Output is correct |
10 |
Correct |
1604 ms |
55520 KB |
Output is correct |
11 |
Correct |
1634 ms |
48696 KB |
Output is correct |
12 |
Correct |
242 ms |
1248 KB |
Output is correct |
13 |
Correct |
1626 ms |
48888 KB |
Output is correct |
14 |
Correct |
788 ms |
1632 KB |
Output is correct |
15 |
Correct |
18 ms |
1248 KB |
Output is correct |
16 |
Correct |
962 ms |
1504 KB |
Output is correct |
17 |
Correct |
1070 ms |
2016 KB |
Output is correct |
18 |
Correct |
944 ms |
1504 KB |
Output is correct |
19 |
Correct |
1080 ms |
1760 KB |
Output is correct |
20 |
Correct |
986 ms |
1760 KB |
Output is correct |
21 |
Correct |
1020 ms |
1744 KB |
Output is correct |
22 |
Correct |
956 ms |
1328 KB |
Output is correct |
23 |
Correct |
978 ms |
1504 KB |
Output is correct |
24 |
Correct |
366 ms |
1272 KB |
Output is correct |
25 |
Correct |
468 ms |
1248 KB |
Output is correct |
26 |
Correct |
754 ms |
23800 KB |
Output is correct |
27 |
Correct |
470 ms |
1760 KB |
Output is correct |
28 |
Correct |
676 ms |
17464 KB |
Output is correct |
29 |
Correct |
458 ms |
1504 KB |
Output is correct |
30 |
Correct |
450 ms |
1768 KB |
Output is correct |
31 |
Correct |
478 ms |
1760 KB |
Output is correct |
32 |
Correct |
994 ms |
38824 KB |
Output is correct |
33 |
Correct |
948 ms |
38576 KB |
Output is correct |
34 |
Correct |
1478 ms |
72816 KB |
Output is correct |
35 |
Correct |
1226 ms |
67256 KB |
Output is correct |
36 |
Correct |
468 ms |
1760 KB |
Output is correct |
37 |
Correct |
18 ms |
1256 KB |
Output is correct |
38 |
Correct |
580 ms |
1248 KB |
Output is correct |
39 |
Correct |
594 ms |
1504 KB |
Output is correct |
40 |
Correct |
602 ms |
1504 KB |
Output is correct |
41 |
Correct |
848 ms |
17672 KB |
Output is correct |
42 |
Correct |
520 ms |
1760 KB |
Output is correct |
43 |
Correct |
888 ms |
17992 KB |
Output is correct |
44 |
Correct |
592 ms |
1768 KB |
Output is correct |
45 |
Correct |
626 ms |
1760 KB |
Output is correct |
46 |
Correct |
1172 ms |
44784 KB |
Output is correct |
47 |
Correct |
1174 ms |
44528 KB |
Output is correct |
48 |
Correct |
1832 ms |
87080 KB |
Output is correct |
49 |
Correct |
1508 ms |
76960 KB |
Output is correct |
50 |
Correct |
530 ms |
1760 KB |
Output is correct |
51 |
Correct |
716 ms |
1568 KB |
Output is correct |
52 |
Correct |
702 ms |
1256 KB |
Output is correct |
53 |
Correct |
1346 ms |
41952 KB |
Output is correct |
54 |
Correct |
724 ms |
1584 KB |
Output is correct |
55 |
Correct |
1162 ms |
37504 KB |
Output is correct |
56 |
Correct |
762 ms |
1760 KB |
Output is correct |
57 |
Correct |
782 ms |
1760 KB |
Output is correct |
58 |
Correct |
768 ms |
1760 KB |
Output is correct |
59 |
Correct |
1344 ms |
49904 KB |
Output is correct |
60 |
Correct |
1320 ms |
49648 KB |
Output is correct |
61 |
Correct |
2028 ms |
97344 KB |
Output is correct |
62 |
Correct |
1712 ms |
89704 KB |
Output is correct |
63 |
Correct |
742 ms |
1752 KB |
Output is correct |
64 |
Correct |
938 ms |
2016 KB |
Output is correct |
65 |
Correct |
1448 ms |
47320 KB |
Output is correct |
66 |
Correct |
1534 ms |
41008 KB |
Output is correct |
67 |
Correct |
792 ms |
2016 KB |
Output is correct |
68 |
Correct |
1048 ms |
2304 KB |
Output is correct |
69 |
Correct |
2262 ms |
95248 KB |
Output is correct |
70 |
Correct |
2232 ms |
79680 KB |
Output is correct |
71 |
Correct |
1068 ms |
10216 KB |
Output is correct |
72 |
Correct |
950 ms |
2784 KB |
Output is correct |