#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
typedef long long int ll;
namespace {
int n;
vector<pair<int,int>> graf[2009];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> djikstra;
int dst[2009];
int wczyt=0,ter=0;
pair<int,int> cel;
int nr=0;
int last=0;
int dom=0;
void napisz(int x, int cnt){
//cout << "A->B " << x << '\n';
for (int i=0;i<cnt;i++) SendA(x & (1<<i));
}
void nast(int v, int d){
//if (nr<10) cout << "A:" << v << ' ' << d << '\n';
dst[v] = d;
last = d;
for (pair<int,int> x:graf[v]){
if (dst[x.first] > d+x.second){
djikstra.push({d+x.second,x.first});
}
}
while(!djikstra.empty() && dst[djikstra.top().second] < 1e9) djikstra.pop();
if (djikstra.empty()){
djikstra.push({(1<<20)-1+last,0});
//if (nr<10) cout << "A empty\n";
}
//if (nr<10) cout << "A->B " << djikstra.top().second << ' ' << djikstra.top().first-last << '\n';
nr++;
}
} // namespace
void InitA(int N, int A, vector<int> U, vector<int> V,
vector<int> C) {
n = N;
for (int x=0;x<A;x++){
graf[U[x]].push_back({V[x],C[x]});
graf[V[x]].push_back({U[x],C[x]});
}
for (int x=0;x<=n;x++) dst[x] = 1e9+9;
nast(0,0);
napisz(djikstra.top().first-last,9);
cel = {-1,-1};
}
void ReceiveA(bool x) {
wczyt += (1<<ter) * x;
ter++;
if (ter==9 && cel.second == -1){
if (djikstra.top().first >= (1<<20)-1 && wczyt == (1<<9)-1) return;
cel.second = wczyt+last;
ter = 0;
wczyt = 0;
if (dom==1) napisz(djikstra.top().first-last,9);
if (djikstra.top().first<=cel.second){
napisz(djikstra.top().second,11);
cel.second = djikstra.top().first;
cel.first = djikstra.top().second;
djikstra.pop();
nast(cel.first,cel.second);
cel = {-1,-1};
dom = 1;
}
}
if (ter==11 && cel.second != -1){
cel.first = wczyt;
wczyt = 0;
ter = 0;
//if (nr<10) cout << "A ma:" << djikstra.top().first << ' ' << djikstra.top().second << '\n';
//if (nr<10) cout << "A dostalo: " << cel.first << ' ' << cel.second << '\n';
//if (nr<10) cout << "A twierdzi o empt: " << apuste << ' ' << bpuste << '\n';
if (min(djikstra.top().first,cel.second) >= (1<<20)-1) return;
nast(cel.first,cel.second);
napisz(djikstra.top().first-last,9);
cel = {-1,-1};
ter = 0;
wczyt = 0;
dom = 0;
}
}
vector<int> Answer() {
vector<int> odp;
for (int x=0;x<n;x++) odp.push_back(dst[x]);
return odp;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace {
int n;
vector<pair<int,int>> graf[2009];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> djikstra;
int dst[2009];
int wczyt=0,ter=0;
pair<int,int> cel;
int nr=0;
int last=0;
int dom=0;
void napisz(int x, int cnt){
//cout << "B->A " << x << '\n';
for (int i=0;i<cnt;i++) SendB(x & (1<<i));
}
void nast(int v, int d){
//if (nr<10) cout << "B:" << v << ' ' << d << '\n';
dst[v] = d;
last = d;
//if (nr<10) cout << "lelum " << poprz << ' ' << d << '\n';
for (pair<int,int> x:graf[v]){
if (dst[x.first] > d+x.second){
djikstra.push({d+x.second,x.first});
}
}
while(!djikstra.empty() && dst[djikstra.top().second] < 1e9) djikstra.pop();
if (djikstra.empty()){
djikstra.push({(1<<20)-1+last,0});
}
//if (nr<10) cout << "B->A " << djikstra.top().second << ' ' << djikstra.top().first-last << '\n';
nr++;
}
} // namespace
void InitB(int N, int B, vector<int> S, vector<int> T,
vector<int> D) {
n = N;
for (int x=0;x<B;x++){
graf[T[x]].push_back({S[x],D[x]});
graf[S[x]].push_back({T[x],D[x]});
}
for (int x=0;x<=n;x++) dst[x] = 1e9+9;
cel = {-1,-1};
djikstra.push({0,0});
nast(0,0);
}
void ReceiveB(bool y) {
wczyt += (1<<ter) * y;
ter++;
if (ter==9 && cel.second == -1){
cel.second = wczyt+last;
if (djikstra.top().first >= (1<<20)-1 && wczyt == (1<<9)-1) return;
wczyt = 0;
ter = 0;
if (dom==0) napisz(djikstra.top().first-last,9);
if (djikstra.top().first<cel.second){
napisz(djikstra.top().second,11);
cel.second = djikstra.top().first;
cel.first = djikstra.top().second;
djikstra.pop();
nast(cel.first,cel.second);
cel = {-1,-1};
dom = 0;
}
}
if (ter==11 && cel.second != -1){
//if (nr<10) cout << "B jestem debilem: " << poprz << '\n';
cel.first = wczyt;
ter = 0;
wczyt = 0;
//if (nr<10) cout << "B ma: " << djikstra.top().first << ' ' << djikstra.top().second << '\n';
//if (nr<10) cout << "B dostalo: " << cel.first << ' ' << cel.second << '\n';
if (min(djikstra.top().first,cel.second) >= (1<<20)-1) return;
//if (nr<10) cout << "nr 2: " << apuste << ' ' << bpuste << '\n';
nast(cel.first,cel.second);
napisz(djikstra.top().first-last,9);
cel = {-1,-1};
dom = 1;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
420 ms |
784 KB |
Output is correct |
2 |
Correct |
2 ms |
656 KB |
Output is correct |
3 |
Correct |
426 ms |
788 KB |
Output is correct |
4 |
Correct |
471 ms |
10120 KB |
Output is correct |
5 |
Correct |
26 ms |
940 KB |
Output is correct |
6 |
Correct |
310 ms |
2332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
656 KB |
Output is correct |
2 |
Correct |
294 ms |
740 KB |
Output is correct |
3 |
Correct |
374 ms |
908 KB |
Output is correct |
4 |
Correct |
542 ms |
27460 KB |
Output is correct |
5 |
Correct |
620 ms |
24328 KB |
Output is correct |
6 |
Correct |
59 ms |
656 KB |
Output is correct |
7 |
Correct |
610 ms |
24596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
423 ms |
728 KB |
Output is correct |
2 |
Correct |
0 ms |
656 KB |
Output is correct |
3 |
Correct |
392 ms |
660 KB |
Output is correct |
4 |
Correct |
410 ms |
744 KB |
Output is correct |
5 |
Correct |
423 ms |
760 KB |
Output is correct |
6 |
Correct |
373 ms |
728 KB |
Output is correct |
7 |
Correct |
289 ms |
744 KB |
Output is correct |
8 |
Correct |
463 ms |
664 KB |
Output is correct |
9 |
Correct |
406 ms |
792 KB |
Output is correct |
10 |
Correct |
465 ms |
784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
161 ms |
684 KB |
Output is correct |
2 |
Correct |
194 ms |
656 KB |
Output is correct |
3 |
Correct |
261 ms |
13308 KB |
Output is correct |
4 |
Correct |
129 ms |
716 KB |
Output is correct |
5 |
Correct |
229 ms |
10108 KB |
Output is correct |
6 |
Correct |
164 ms |
656 KB |
Output is correct |
7 |
Correct |
192 ms |
656 KB |
Output is correct |
8 |
Correct |
183 ms |
656 KB |
Output is correct |
9 |
Correct |
343 ms |
19432 KB |
Output is correct |
10 |
Correct |
374 ms |
19476 KB |
Output is correct |
11 |
Correct |
461 ms |
38308 KB |
Output is correct |
12 |
Correct |
430 ms |
36008 KB |
Output is correct |
13 |
Correct |
165 ms |
656 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
161 ms |
684 KB |
Output is correct |
2 |
Correct |
194 ms |
656 KB |
Output is correct |
3 |
Correct |
261 ms |
13308 KB |
Output is correct |
4 |
Correct |
129 ms |
716 KB |
Output is correct |
5 |
Correct |
229 ms |
10108 KB |
Output is correct |
6 |
Correct |
164 ms |
656 KB |
Output is correct |
7 |
Correct |
192 ms |
656 KB |
Output is correct |
8 |
Correct |
183 ms |
656 KB |
Output is correct |
9 |
Correct |
343 ms |
19432 KB |
Output is correct |
10 |
Correct |
374 ms |
19476 KB |
Output is correct |
11 |
Correct |
461 ms |
38308 KB |
Output is correct |
12 |
Correct |
430 ms |
36008 KB |
Output is correct |
13 |
Correct |
165 ms |
656 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
15 |
Correct |
225 ms |
696 KB |
Output is correct |
16 |
Correct |
210 ms |
720 KB |
Output is correct |
17 |
Correct |
215 ms |
720 KB |
Output is correct |
18 |
Correct |
311 ms |
10020 KB |
Output is correct |
19 |
Correct |
226 ms |
720 KB |
Output is correct |
20 |
Correct |
323 ms |
10284 KB |
Output is correct |
21 |
Correct |
187 ms |
740 KB |
Output is correct |
22 |
Correct |
257 ms |
748 KB |
Output is correct |
23 |
Correct |
410 ms |
22448 KB |
Output is correct |
24 |
Correct |
365 ms |
22336 KB |
Output is correct |
25 |
Correct |
575 ms |
44220 KB |
Output is correct |
26 |
Correct |
538 ms |
40528 KB |
Output is correct |
27 |
Correct |
246 ms |
872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
161 ms |
684 KB |
Output is correct |
2 |
Correct |
194 ms |
656 KB |
Output is correct |
3 |
Correct |
261 ms |
13308 KB |
Output is correct |
4 |
Correct |
129 ms |
716 KB |
Output is correct |
5 |
Correct |
229 ms |
10108 KB |
Output is correct |
6 |
Correct |
164 ms |
656 KB |
Output is correct |
7 |
Correct |
192 ms |
656 KB |
Output is correct |
8 |
Correct |
183 ms |
656 KB |
Output is correct |
9 |
Correct |
343 ms |
19432 KB |
Output is correct |
10 |
Correct |
374 ms |
19476 KB |
Output is correct |
11 |
Correct |
461 ms |
38308 KB |
Output is correct |
12 |
Correct |
430 ms |
36008 KB |
Output is correct |
13 |
Correct |
165 ms |
656 KB |
Output is correct |
14 |
Correct |
0 ms |
656 KB |
Output is correct |
15 |
Correct |
225 ms |
696 KB |
Output is correct |
16 |
Correct |
210 ms |
720 KB |
Output is correct |
17 |
Correct |
215 ms |
720 KB |
Output is correct |
18 |
Correct |
311 ms |
10020 KB |
Output is correct |
19 |
Correct |
226 ms |
720 KB |
Output is correct |
20 |
Correct |
323 ms |
10284 KB |
Output is correct |
21 |
Correct |
187 ms |
740 KB |
Output is correct |
22 |
Correct |
257 ms |
748 KB |
Output is correct |
23 |
Correct |
410 ms |
22448 KB |
Output is correct |
24 |
Correct |
365 ms |
22336 KB |
Output is correct |
25 |
Correct |
575 ms |
44220 KB |
Output is correct |
26 |
Correct |
538 ms |
40528 KB |
Output is correct |
27 |
Correct |
246 ms |
872 KB |
Output is correct |
28 |
Correct |
271 ms |
704 KB |
Output is correct |
29 |
Correct |
308 ms |
664 KB |
Output is correct |
30 |
Correct |
492 ms |
24088 KB |
Output is correct |
31 |
Correct |
230 ms |
664 KB |
Output is correct |
32 |
Correct |
472 ms |
20992 KB |
Output is correct |
33 |
Correct |
274 ms |
736 KB |
Output is correct |
34 |
Correct |
279 ms |
768 KB |
Output is correct |
35 |
Correct |
258 ms |
840 KB |
Output is correct |
36 |
Correct |
437 ms |
24980 KB |
Output is correct |
37 |
Correct |
483 ms |
25088 KB |
Output is correct |
38 |
Correct |
709 ms |
49408 KB |
Output is correct |
39 |
Correct |
653 ms |
47200 KB |
Output is correct |
40 |
Correct |
264 ms |
1032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
420 ms |
784 KB |
Output is correct |
2 |
Correct |
2 ms |
656 KB |
Output is correct |
3 |
Correct |
426 ms |
788 KB |
Output is correct |
4 |
Correct |
471 ms |
10120 KB |
Output is correct |
5 |
Correct |
26 ms |
940 KB |
Output is correct |
6 |
Correct |
310 ms |
2332 KB |
Output is correct |
7 |
Correct |
2 ms |
656 KB |
Output is correct |
8 |
Correct |
294 ms |
740 KB |
Output is correct |
9 |
Correct |
374 ms |
908 KB |
Output is correct |
10 |
Correct |
542 ms |
27460 KB |
Output is correct |
11 |
Correct |
620 ms |
24328 KB |
Output is correct |
12 |
Correct |
59 ms |
656 KB |
Output is correct |
13 |
Correct |
610 ms |
24596 KB |
Output is correct |
14 |
Correct |
423 ms |
728 KB |
Output is correct |
15 |
Correct |
0 ms |
656 KB |
Output is correct |
16 |
Correct |
392 ms |
660 KB |
Output is correct |
17 |
Correct |
410 ms |
744 KB |
Output is correct |
18 |
Correct |
423 ms |
760 KB |
Output is correct |
19 |
Correct |
373 ms |
728 KB |
Output is correct |
20 |
Correct |
289 ms |
744 KB |
Output is correct |
21 |
Correct |
463 ms |
664 KB |
Output is correct |
22 |
Correct |
406 ms |
792 KB |
Output is correct |
23 |
Correct |
465 ms |
784 KB |
Output is correct |
24 |
Correct |
161 ms |
684 KB |
Output is correct |
25 |
Correct |
194 ms |
656 KB |
Output is correct |
26 |
Correct |
261 ms |
13308 KB |
Output is correct |
27 |
Correct |
129 ms |
716 KB |
Output is correct |
28 |
Correct |
229 ms |
10108 KB |
Output is correct |
29 |
Correct |
164 ms |
656 KB |
Output is correct |
30 |
Correct |
192 ms |
656 KB |
Output is correct |
31 |
Correct |
183 ms |
656 KB |
Output is correct |
32 |
Correct |
343 ms |
19432 KB |
Output is correct |
33 |
Correct |
374 ms |
19476 KB |
Output is correct |
34 |
Correct |
461 ms |
38308 KB |
Output is correct |
35 |
Correct |
430 ms |
36008 KB |
Output is correct |
36 |
Correct |
165 ms |
656 KB |
Output is correct |
37 |
Correct |
0 ms |
656 KB |
Output is correct |
38 |
Correct |
225 ms |
696 KB |
Output is correct |
39 |
Correct |
210 ms |
720 KB |
Output is correct |
40 |
Correct |
215 ms |
720 KB |
Output is correct |
41 |
Correct |
311 ms |
10020 KB |
Output is correct |
42 |
Correct |
226 ms |
720 KB |
Output is correct |
43 |
Correct |
323 ms |
10284 KB |
Output is correct |
44 |
Correct |
187 ms |
740 KB |
Output is correct |
45 |
Correct |
257 ms |
748 KB |
Output is correct |
46 |
Correct |
410 ms |
22448 KB |
Output is correct |
47 |
Correct |
365 ms |
22336 KB |
Output is correct |
48 |
Correct |
575 ms |
44220 KB |
Output is correct |
49 |
Correct |
538 ms |
40528 KB |
Output is correct |
50 |
Correct |
246 ms |
872 KB |
Output is correct |
51 |
Correct |
271 ms |
704 KB |
Output is correct |
52 |
Correct |
308 ms |
664 KB |
Output is correct |
53 |
Correct |
492 ms |
24088 KB |
Output is correct |
54 |
Correct |
230 ms |
664 KB |
Output is correct |
55 |
Correct |
472 ms |
20992 KB |
Output is correct |
56 |
Correct |
274 ms |
736 KB |
Output is correct |
57 |
Correct |
279 ms |
768 KB |
Output is correct |
58 |
Correct |
258 ms |
840 KB |
Output is correct |
59 |
Correct |
437 ms |
24980 KB |
Output is correct |
60 |
Correct |
483 ms |
25088 KB |
Output is correct |
61 |
Correct |
709 ms |
49408 KB |
Output is correct |
62 |
Correct |
653 ms |
47200 KB |
Output is correct |
63 |
Correct |
264 ms |
1032 KB |
Output is correct |
64 |
Correct |
399 ms |
952 KB |
Output is correct |
65 |
Correct |
581 ms |
26504 KB |
Output is correct |
66 |
Correct |
605 ms |
23316 KB |
Output is correct |
67 |
Correct |
434 ms |
936 KB |
Output is correct |
68 |
Correct |
470 ms |
936 KB |
Output is correct |
69 |
Correct |
810 ms |
48280 KB |
Output is correct |
70 |
Correct |
819 ms |
41228 KB |
Output is correct |
71 |
Correct |
427 ms |
5616 KB |
Output is correct |
72 |
Correct |
370 ms |
1340 KB |
Output is correct |