#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
namespace {
int N;
vpii adj[2005];
int dist[2005],done[2005];
int count = 1;
int global = 0;
int pend;
int pendtype; // 0 = dist,1 = node
int verA,distA,verB,distB;
PQD(pii) pq;
void send(int x, int len){
if(x >= (1<<len)) x = (1<<len)-1;
FORD(i,len-1,0) SendA((x>>i)&1);
}
void refresh(){
while(pq.size()){
int u = pq.top().S;
pq.pop();
for(auto v:adj[u]){
if(dist[v.F] > dist[u]+v.S){
dist[v.F] = dist[u]+v.S;
pq.push({dist[v.F],v.F});
}
}
}
verB = 0;
distB = 0;
}
void do_next(){
if(count == N) return;
count++;
refresh();
int u = -1;
REP(i,N){
if(done[i]) continue;
if(u == -1 or dist[i] < dist[u]) u = i;
}
pend = 9;
pendtype = 0;
verA = u;
distA = dist[u];
// cerr << "Azer send dist: " << distA << endl;
send(min(distA-global,(1<<9)-1),9);
}
} // namespace
void InitA(int N, int A, vi U, vi V, vi C) {
::N = N;
REP(i,A){
adj[U[i]].pb({V[i],C[i]});
adj[V[i]].pb({U[i],C[i]});
}
REP(i,N) dist[i] = (1<<20)-1;
dist[0] = 0;
done[0] = 1;
pq.push({0,0});
do_next();
}
void ReceiveA(bool x){
pend--;
if(pendtype == 1){
verB += ((int) x)*(1<<(pend));
if(pend == 0){
dist[verB] = distB;
done[verB] = 1;
pq.push({distB,verB});
refresh();
do_next();
}
}
else{
distB += ((int) x)*(1<<(pend));
if(pend == 0){
distB += global;
if(distA < distB){
global = distA;
done[verA] = 1;
// cerr << "Azer send ver: " << verA << endl;
send(verA,11);
do_next();
}
else{
global = distB;
pend = 11;
pendtype = 1;
}
}
}
}
vi Answer() {
vi vd;
REP(i,N) vd.pb(dist[i]);
return vd;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
namespace {
int N;
vpii adj[2005];
int dist[2005],done[2005];
int pend = 9;
int pendtype = 0; // 0 = dist,1 = node
int global = 0;
int verA,distA,verB,distB;
PQD(pii) pq;
void send(int x, int len){
if(x >= (1<<len)) x = (1<<len)-1;
FORD(i,len-1,0) SendB((x>>i)&1);
}
void refresh(){
while(pq.size()){
int u = pq.top().S;
pq.pop();
for(auto v:adj[u]){
if(dist[v.F] > dist[u]+v.S){
dist[v.F] = dist[u]+v.S;
pq.push({dist[v.F],v.F});
}
}
}
verA = 0;
distA = 0;
}
void do_next(){
int u = -1;
REP(i,N){
if(done[i]) continue;
if(u == -1 or dist[i] < dist[u]) u = i;
}
verB = u;
distB = dist[u];
int diff = distB-global;
if(distA < distB){
global = distA;
pend = 11;
pendtype = 1;
// cerr << "Baijan send dist: " << distB << endl;
send(min(diff,(1<<9)-1),9);
}
else{
dist[verB] = distB;
done[verB] = 1;
global = distB;
refresh();
pend = 9;
pendtype = 0;
// cerr << "Baijan send dist: " << distB << endl;
// cerr << "Baijan send ver: " << verB << endl;
send(min(diff,(1<<9)-1),9);
send(verB,11);
}
}
} // namespace
void InitB(int N, int B, vi S, vi T, vi D) {
::N = N;
REP(i,B){
adj[S[i]].pb({T[i],D[i]});
adj[T[i]].pb({S[i],D[i]});
}
REP(i,N) dist[i] = (1<<20)-1;
dist[0] = 0;
done[0] = 1;
pq.push({0,0});
refresh();
}
void ReceiveB(bool y) {
pend--;
if(pendtype == 1){
verA += ((int) y)*(1<<(pend));
if(pend == 0){
dist[verA] = distA;
done[verA] = 1;
pq.push({distA,verA});
refresh();
pend = 9;
pendtype = 11;
}
}
else{
distA += ((int) y)*(1<<(pend));
if(pend == 0){
distA += global;
do_next();
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1196 ms |
1792 KB |
Output is correct |
2 |
Correct |
16 ms |
1280 KB |
Output is correct |
3 |
Correct |
1004 ms |
1872 KB |
Output is correct |
4 |
Correct |
1312 ms |
20512 KB |
Output is correct |
5 |
Correct |
90 ms |
2048 KB |
Output is correct |
6 |
Correct |
1260 ms |
4944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1536 KB |
Output is correct |
2 |
Correct |
1482 ms |
1744 KB |
Output is correct |
3 |
Correct |
1326 ms |
1792 KB |
Output is correct |
4 |
Correct |
1537 ms |
55304 KB |
Output is correct |
5 |
Correct |
1804 ms |
48752 KB |
Output is correct |
6 |
Correct |
297 ms |
1792 KB |
Output is correct |
7 |
Correct |
1606 ms |
48936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1318 ms |
1792 KB |
Output is correct |
2 |
Correct |
18 ms |
1536 KB |
Output is correct |
3 |
Correct |
1134 ms |
1592 KB |
Output is correct |
4 |
Correct |
1202 ms |
1792 KB |
Output is correct |
5 |
Correct |
1346 ms |
1792 KB |
Output is correct |
6 |
Correct |
1332 ms |
1536 KB |
Output is correct |
7 |
Correct |
1040 ms |
1792 KB |
Output is correct |
8 |
Correct |
1368 ms |
1792 KB |
Output is correct |
9 |
Correct |
1084 ms |
1792 KB |
Output is correct |
10 |
Correct |
1332 ms |
2016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
1536 KB |
Output is correct |
2 |
Correct |
454 ms |
1536 KB |
Output is correct |
3 |
Correct |
811 ms |
23808 KB |
Output is correct |
4 |
Correct |
632 ms |
1536 KB |
Output is correct |
5 |
Correct |
768 ms |
17464 KB |
Output is correct |
6 |
Correct |
516 ms |
1792 KB |
Output is correct |
7 |
Correct |
552 ms |
1856 KB |
Output is correct |
8 |
Correct |
470 ms |
1792 KB |
Output is correct |
9 |
Correct |
868 ms |
36144 KB |
Output is correct |
10 |
Correct |
898 ms |
36264 KB |
Output is correct |
11 |
Correct |
1112 ms |
61992 KB |
Output is correct |
12 |
Correct |
1169 ms |
54264 KB |
Output is correct |
13 |
Correct |
605 ms |
2304 KB |
Output is correct |
14 |
Correct |
18 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
1536 KB |
Output is correct |
2 |
Correct |
454 ms |
1536 KB |
Output is correct |
3 |
Correct |
811 ms |
23808 KB |
Output is correct |
4 |
Correct |
632 ms |
1536 KB |
Output is correct |
5 |
Correct |
768 ms |
17464 KB |
Output is correct |
6 |
Correct |
516 ms |
1792 KB |
Output is correct |
7 |
Correct |
552 ms |
1856 KB |
Output is correct |
8 |
Correct |
470 ms |
1792 KB |
Output is correct |
9 |
Correct |
868 ms |
36144 KB |
Output is correct |
10 |
Correct |
898 ms |
36264 KB |
Output is correct |
11 |
Correct |
1112 ms |
61992 KB |
Output is correct |
12 |
Correct |
1169 ms |
54264 KB |
Output is correct |
13 |
Correct |
605 ms |
2304 KB |
Output is correct |
14 |
Correct |
18 ms |
1280 KB |
Output is correct |
15 |
Correct |
681 ms |
1800 KB |
Output is correct |
16 |
Correct |
540 ms |
1792 KB |
Output is correct |
17 |
Correct |
620 ms |
1760 KB |
Output is correct |
18 |
Correct |
908 ms |
17848 KB |
Output is correct |
19 |
Correct |
595 ms |
1808 KB |
Output is correct |
20 |
Correct |
784 ms |
18000 KB |
Output is correct |
21 |
Correct |
589 ms |
2016 KB |
Output is correct |
22 |
Correct |
592 ms |
1792 KB |
Output is correct |
23 |
Correct |
1036 ms |
44520 KB |
Output is correct |
24 |
Correct |
1022 ms |
44312 KB |
Output is correct |
25 |
Correct |
1388 ms |
75760 KB |
Output is correct |
26 |
Correct |
1092 ms |
64816 KB |
Output is correct |
27 |
Correct |
812 ms |
1792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
538 ms |
1536 KB |
Output is correct |
2 |
Correct |
454 ms |
1536 KB |
Output is correct |
3 |
Correct |
811 ms |
23808 KB |
Output is correct |
4 |
Correct |
632 ms |
1536 KB |
Output is correct |
5 |
Correct |
768 ms |
17464 KB |
Output is correct |
6 |
Correct |
516 ms |
1792 KB |
Output is correct |
7 |
Correct |
552 ms |
1856 KB |
Output is correct |
8 |
Correct |
470 ms |
1792 KB |
Output is correct |
9 |
Correct |
868 ms |
36144 KB |
Output is correct |
10 |
Correct |
898 ms |
36264 KB |
Output is correct |
11 |
Correct |
1112 ms |
61992 KB |
Output is correct |
12 |
Correct |
1169 ms |
54264 KB |
Output is correct |
13 |
Correct |
605 ms |
2304 KB |
Output is correct |
14 |
Correct |
18 ms |
1280 KB |
Output is correct |
15 |
Correct |
681 ms |
1800 KB |
Output is correct |
16 |
Correct |
540 ms |
1792 KB |
Output is correct |
17 |
Correct |
620 ms |
1760 KB |
Output is correct |
18 |
Correct |
908 ms |
17848 KB |
Output is correct |
19 |
Correct |
595 ms |
1808 KB |
Output is correct |
20 |
Correct |
784 ms |
18000 KB |
Output is correct |
21 |
Correct |
589 ms |
2016 KB |
Output is correct |
22 |
Correct |
592 ms |
1792 KB |
Output is correct |
23 |
Correct |
1036 ms |
44520 KB |
Output is correct |
24 |
Correct |
1022 ms |
44312 KB |
Output is correct |
25 |
Correct |
1388 ms |
75760 KB |
Output is correct |
26 |
Correct |
1092 ms |
64816 KB |
Output is correct |
27 |
Correct |
812 ms |
1792 KB |
Output is correct |
28 |
Correct |
692 ms |
1672 KB |
Output is correct |
29 |
Correct |
826 ms |
1536 KB |
Output is correct |
30 |
Correct |
1262 ms |
42544 KB |
Output is correct |
31 |
Correct |
764 ms |
1760 KB |
Output is correct |
32 |
Correct |
1258 ms |
37688 KB |
Output is correct |
33 |
Correct |
884 ms |
1752 KB |
Output is correct |
34 |
Correct |
810 ms |
1792 KB |
Output is correct |
35 |
Correct |
890 ms |
2272 KB |
Output is correct |
36 |
Correct |
1218 ms |
49632 KB |
Output is correct |
37 |
Correct |
1174 ms |
49640 KB |
Output is correct |
38 |
Correct |
1632 ms |
86512 KB |
Output is correct |
39 |
Correct |
1466 ms |
79224 KB |
Output is correct |
40 |
Correct |
768 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1196 ms |
1792 KB |
Output is correct |
2 |
Correct |
16 ms |
1280 KB |
Output is correct |
3 |
Correct |
1004 ms |
1872 KB |
Output is correct |
4 |
Correct |
1312 ms |
20512 KB |
Output is correct |
5 |
Correct |
90 ms |
2048 KB |
Output is correct |
6 |
Correct |
1260 ms |
4944 KB |
Output is correct |
7 |
Correct |
18 ms |
1536 KB |
Output is correct |
8 |
Correct |
1482 ms |
1744 KB |
Output is correct |
9 |
Correct |
1326 ms |
1792 KB |
Output is correct |
10 |
Correct |
1537 ms |
55304 KB |
Output is correct |
11 |
Correct |
1804 ms |
48752 KB |
Output is correct |
12 |
Correct |
297 ms |
1792 KB |
Output is correct |
13 |
Correct |
1606 ms |
48936 KB |
Output is correct |
14 |
Correct |
1318 ms |
1792 KB |
Output is correct |
15 |
Correct |
18 ms |
1536 KB |
Output is correct |
16 |
Correct |
1134 ms |
1592 KB |
Output is correct |
17 |
Correct |
1202 ms |
1792 KB |
Output is correct |
18 |
Correct |
1346 ms |
1792 KB |
Output is correct |
19 |
Correct |
1332 ms |
1536 KB |
Output is correct |
20 |
Correct |
1040 ms |
1792 KB |
Output is correct |
21 |
Correct |
1368 ms |
1792 KB |
Output is correct |
22 |
Correct |
1084 ms |
1792 KB |
Output is correct |
23 |
Correct |
1332 ms |
2016 KB |
Output is correct |
24 |
Correct |
538 ms |
1536 KB |
Output is correct |
25 |
Correct |
454 ms |
1536 KB |
Output is correct |
26 |
Correct |
811 ms |
23808 KB |
Output is correct |
27 |
Correct |
632 ms |
1536 KB |
Output is correct |
28 |
Correct |
768 ms |
17464 KB |
Output is correct |
29 |
Correct |
516 ms |
1792 KB |
Output is correct |
30 |
Correct |
552 ms |
1856 KB |
Output is correct |
31 |
Correct |
470 ms |
1792 KB |
Output is correct |
32 |
Correct |
868 ms |
36144 KB |
Output is correct |
33 |
Correct |
898 ms |
36264 KB |
Output is correct |
34 |
Correct |
1112 ms |
61992 KB |
Output is correct |
35 |
Correct |
1169 ms |
54264 KB |
Output is correct |
36 |
Correct |
605 ms |
2304 KB |
Output is correct |
37 |
Correct |
18 ms |
1280 KB |
Output is correct |
38 |
Correct |
681 ms |
1800 KB |
Output is correct |
39 |
Correct |
540 ms |
1792 KB |
Output is correct |
40 |
Correct |
620 ms |
1760 KB |
Output is correct |
41 |
Correct |
908 ms |
17848 KB |
Output is correct |
42 |
Correct |
595 ms |
1808 KB |
Output is correct |
43 |
Correct |
784 ms |
18000 KB |
Output is correct |
44 |
Correct |
589 ms |
2016 KB |
Output is correct |
45 |
Correct |
592 ms |
1792 KB |
Output is correct |
46 |
Correct |
1036 ms |
44520 KB |
Output is correct |
47 |
Correct |
1022 ms |
44312 KB |
Output is correct |
48 |
Correct |
1388 ms |
75760 KB |
Output is correct |
49 |
Correct |
1092 ms |
64816 KB |
Output is correct |
50 |
Correct |
812 ms |
1792 KB |
Output is correct |
51 |
Correct |
692 ms |
1672 KB |
Output is correct |
52 |
Correct |
826 ms |
1536 KB |
Output is correct |
53 |
Correct |
1262 ms |
42544 KB |
Output is correct |
54 |
Correct |
764 ms |
1760 KB |
Output is correct |
55 |
Correct |
1258 ms |
37688 KB |
Output is correct |
56 |
Correct |
884 ms |
1752 KB |
Output is correct |
57 |
Correct |
810 ms |
1792 KB |
Output is correct |
58 |
Correct |
890 ms |
2272 KB |
Output is correct |
59 |
Correct |
1218 ms |
49632 KB |
Output is correct |
60 |
Correct |
1174 ms |
49640 KB |
Output is correct |
61 |
Correct |
1632 ms |
86512 KB |
Output is correct |
62 |
Correct |
1466 ms |
79224 KB |
Output is correct |
63 |
Correct |
768 ms |
2048 KB |
Output is correct |
64 |
Correct |
1468 ms |
2304 KB |
Output is correct |
65 |
Correct |
1578 ms |
47328 KB |
Output is correct |
66 |
Correct |
1558 ms |
41088 KB |
Output is correct |
67 |
Correct |
1050 ms |
2560 KB |
Output is correct |
68 |
Correct |
1270 ms |
2400 KB |
Output is correct |
69 |
Correct |
2250 ms |
83952 KB |
Output is correct |
70 |
Correct |
1986 ms |
69008 KB |
Output is correct |
71 |
Correct |
1040 ms |
9664 KB |
Output is correct |
72 |
Correct |
1444 ms |
2560 KB |
Output is correct |