#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e3 + 5, inf = 1e9 + 5;
using pii = pair<int,int>;
namespace A {
int N;
set<pii> heap;
vector<pii> g[nmax];
int dist[nmax];
vector<int> bits;
int lastdocumented = 0;
int last = 0;
int state = 0;
int theircost = 0, theirnode = 0;
int mynode = 0, mycost = 0;
void receiveA(bool x) {
bits.emplace_back(x);
if(state == 0 && bits.size() == lastdocumented + 9) {
int node, cost;
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
cost -= last;
theircost = 0;
for(int i = lastdocumented; i < bits.size(); i++) theircost = (theircost << 1) | bits[i];
lastdocumented = bits.size();
//cerr << "For A: " << node << ' ' << cost << "//" << theircost << '\n';
if(min(cost, theircost) == 511)
return;
//cerr << "arrived here " << lastdocumented << ' ' << theircost << ' ' << cost << ' ' << node << '\n';
if(theircost < cost) {
state = 1;
mycost = theircost;
return;
}
else {
for(int i = 10; i >= 0; i--) SendA((node & (1 << i)) > 0);
heap.erase(heap.begin());
mynode = node;
mycost = cost;
}
state = 2;
}
if(state == 1 && lastdocumented + 11 == bits.size()) {
mynode = 0;
for(int i = lastdocumented; i < bits.size(); i++)
mynode = (mynode << 1) | bits[i];
state = 2;
}
if(state == 2) {
auto [node, cost] = pii{mynode, mycost};
if(cost == 511)
return;
if(heap.count(pii{dist[node], node}))
heap.erase(heap.find(pii{dist[node], node}));
dist[node] = cost + last;
//cerr << "A continues with " << node << " + " << dist[node] << '\n';
//cerr << node << ' ' << cost + last << '\n';
for(auto [x, c] : g[node]) {
if(dist[x] > dist[node] + c) {
if(heap.count(pii{dist[x], x}))
heap.erase(heap.find(pii{dist[x], x}));
dist[x] = dist[node] + c;
heap.emplace(dist[x], x);
}
}
last = dist[node];
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
//cerr << "A pushes: " << node << ' ' << cost << "/" << last << '\n';
cost -= last;
for(int i = 8; i >= 0; i--) SendA((cost & (1 << i)) > 0);
state = 0;
lastdocumented = bits.size();
}
}
} // namespace
void ReceiveA(bool x) { A::receiveA(x); }
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
A::N = N;
for (int i = 0; i < A; ++i) {
A::g[U[i]].emplace_back(V[i], C[i]);
A::g[V[i]].emplace_back(U[i], C[i]);
}
for(int i = 0; i < N; i++) A::dist[i] = inf;
A::dist[0] = 0;
A::heap.emplace(0, 0);
for(int i = 0; i < 9; i++)
SendA(0);
return;
}
std::vector<int> Answer() {
std::vector<int> ans(A::N);
for (int k = 0; k < A::N; ++k) {
ans[k] = A::dist[k];
}
return ans;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define nmax sdioh
#define inf sdiohah
const int nmax = 2e3 + 5, inf = 1e9 + 5;
using pii = pair<int,int>;
namespace B {
int N;
set<pii> heap;
vector<pii> g[nmax];
int dist[nmax];
vector<int> bits;
int lastdocumented = 0;
int last = 0;
int state = 0;
int theircost = 0, theirnode = 0;
int mynode = 0, mycost = 0;
void receiveB(bool x) {
bits.emplace_back(x);
if(state == 0 && bits.size() == lastdocumented + 9) {
int node, cost;
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
cost -= last;
theircost = 0;
for(int i = lastdocumented; i < bits.size(); i++) theircost = (theircost << 1) | bits[i];
lastdocumented = bits.size();
//cerr << "For B: " << node << ' ' << cost << "//" << theircost << '\n';
if(min(cost, theircost) == 511)
return;
if(theircost <= cost) {
state = 1;
mycost = theircost;
return;
}
else {
for(int i = 10; i >= 0; i--) SendB((node & (1 << i)) > 0);
heap.erase(heap.begin());
mynode = node;
mycost = cost;
}
state = 2;
}
//else if(state == 1) { cerr << lastdocumented << ' ' << bits.size() << '\n'; }
if(state == 1 && lastdocumented + 11 == bits.size()) {
mynode = 0;
for(int i = lastdocumented; i < bits.size(); i++)
mynode = (mynode << 1) | bits[i];
state = 2;
}
if(state == 2) {
auto [node, cost] = pii{mynode, mycost};
if(cost == 511)
return;
if(heap.count(pii{dist[node], node}))
heap.erase(heap.find(pii{dist[node], node}));
dist[node] = cost + last;
//cerr << "B continues with " << node << " + " << dist[node] << '\n';
for(auto [x, c] : g[node]) {
if(dist[x] > dist[node] + c) {
if(heap.count(pii{dist[x], x}))
heap.erase(heap.find(pii{dist[x], x}));
dist[x] = dist[node] + c;
heap.emplace(dist[x], x);
}
}
last = dist[node];
if(heap.size())
tie(cost, node) = *heap.begin();
else
node = N, cost = 511 + last;
cost -= last;
for(int i = 8; i >= 0; i--) SendB((cost & (1 << i)) > 0);
state = 0;
lastdocumented = bits.size();
}
}
} // namespace
void ReceiveB(bool x) { B::receiveB(x); }
void InitB(int N, int B, std::vector<int> U, std::vector<int> V,
std::vector<int> C) {
B::N = N;
for (int i = 0; i < B; ++i) {
B::g[U[i]].emplace_back(V[i], C[i]);
B::g[V[i]].emplace_back(U[i], C[i]);
}
for(int i = 0; i < N; i++) B::dist[i] = inf;
B::dist[0] = 0;
B::heap.emplace(0, 0);
for(int i = 0; i < 9; i++)
SendB(0);
return;
}
Compilation message
Azer.cpp: In function 'void A::receiveA(bool)':
Azer.cpp:24:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
24 | if(state == 0 && bits.size() == lastdocumented + 9) {
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Azer.cpp:32:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i = lastdocumented; i < bits.size(); i++) theircost = (theircost << 1) | bits[i];
| ~~^~~~~~~~~~~~~
Azer.cpp:51:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if(state == 1 && lastdocumented + 11 == bits.size()) {
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
Azer.cpp:53:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = lastdocumented; i < bits.size(); i++)
| ~~^~~~~~~~~~~~~
Azer.cpp:58:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | auto [node, cost] = pii{mynode, mycost};
| ^
Azer.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for(auto [x, c] : g[node]) {
| ^
Baijan.cpp: In function 'void B::receiveB(bool)':
Baijan.cpp:25:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
25 | if(state == 0 && bits.size() == lastdocumented + 9) {
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Baijan.cpp:33:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = lastdocumented; i < bits.size(); i++) theircost = (theircost << 1) | bits[i];
| ~~^~~~~~~~~~~~~
Baijan.cpp:52:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if(state == 1 && lastdocumented + 11 == bits.size()) {
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
Baijan.cpp:54:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = lastdocumented; i < bits.size(); i++)
| ~~^~~~~~~~~~~~~
Baijan.cpp:59:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | auto [node, cost] = pii{mynode, mycost};
| ^
Baijan.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | for(auto [x, c] : g[node]) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
340 ms |
904 KB |
Execution killed with signal 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
656 KB |
Output is correct |
2 |
Runtime error |
251 ms |
756 KB |
Execution killed with signal 13 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
129 ms |
628 KB |
Wrong Answer [2] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
188 ms |
980 KB |
Output is correct |
2 |
Correct |
218 ms |
1028 KB |
Output is correct |
3 |
Correct |
277 ms |
13244 KB |
Output is correct |
4 |
Correct |
147 ms |
1008 KB |
Output is correct |
5 |
Correct |
278 ms |
10124 KB |
Output is correct |
6 |
Correct |
237 ms |
944 KB |
Output is correct |
7 |
Correct |
234 ms |
1044 KB |
Output is correct |
8 |
Correct |
225 ms |
1128 KB |
Output is correct |
9 |
Correct |
306 ms |
18308 KB |
Output is correct |
10 |
Correct |
324 ms |
18344 KB |
Output is correct |
11 |
Correct |
375 ms |
35708 KB |
Output is correct |
12 |
Correct |
381 ms |
30568 KB |
Output is correct |
13 |
Correct |
224 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
188 ms |
980 KB |
Output is correct |
2 |
Correct |
218 ms |
1028 KB |
Output is correct |
3 |
Correct |
277 ms |
13244 KB |
Output is correct |
4 |
Correct |
147 ms |
1008 KB |
Output is correct |
5 |
Correct |
278 ms |
10124 KB |
Output is correct |
6 |
Correct |
237 ms |
944 KB |
Output is correct |
7 |
Correct |
234 ms |
1044 KB |
Output is correct |
8 |
Correct |
225 ms |
1128 KB |
Output is correct |
9 |
Correct |
306 ms |
18308 KB |
Output is correct |
10 |
Correct |
324 ms |
18344 KB |
Output is correct |
11 |
Correct |
375 ms |
35708 KB |
Output is correct |
12 |
Correct |
381 ms |
30568 KB |
Output is correct |
13 |
Correct |
224 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
656 KB |
Output is correct |
15 |
Correct |
253 ms |
976 KB |
Output is correct |
16 |
Correct |
285 ms |
1116 KB |
Output is correct |
17 |
Correct |
242 ms |
1172 KB |
Output is correct |
18 |
Correct |
343 ms |
10120 KB |
Output is correct |
19 |
Correct |
219 ms |
1040 KB |
Output is correct |
20 |
Correct |
351 ms |
10368 KB |
Output is correct |
21 |
Correct |
310 ms |
1412 KB |
Output is correct |
22 |
Correct |
229 ms |
1252 KB |
Output is correct |
23 |
Correct |
380 ms |
22384 KB |
Output is correct |
24 |
Correct |
416 ms |
22560 KB |
Output is correct |
25 |
Correct |
487 ms |
43588 KB |
Output is correct |
26 |
Correct |
373 ms |
36488 KB |
Output is correct |
27 |
Correct |
309 ms |
1296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
188 ms |
980 KB |
Output is correct |
2 |
Correct |
218 ms |
1028 KB |
Output is correct |
3 |
Correct |
277 ms |
13244 KB |
Output is correct |
4 |
Correct |
147 ms |
1008 KB |
Output is correct |
5 |
Correct |
278 ms |
10124 KB |
Output is correct |
6 |
Correct |
237 ms |
944 KB |
Output is correct |
7 |
Correct |
234 ms |
1044 KB |
Output is correct |
8 |
Correct |
225 ms |
1128 KB |
Output is correct |
9 |
Correct |
306 ms |
18308 KB |
Output is correct |
10 |
Correct |
324 ms |
18344 KB |
Output is correct |
11 |
Correct |
375 ms |
35708 KB |
Output is correct |
12 |
Correct |
381 ms |
30568 KB |
Output is correct |
13 |
Correct |
224 ms |
852 KB |
Output is correct |
14 |
Correct |
2 ms |
656 KB |
Output is correct |
15 |
Correct |
253 ms |
976 KB |
Output is correct |
16 |
Correct |
285 ms |
1116 KB |
Output is correct |
17 |
Correct |
242 ms |
1172 KB |
Output is correct |
18 |
Correct |
343 ms |
10120 KB |
Output is correct |
19 |
Correct |
219 ms |
1040 KB |
Output is correct |
20 |
Correct |
351 ms |
10368 KB |
Output is correct |
21 |
Correct |
310 ms |
1412 KB |
Output is correct |
22 |
Correct |
229 ms |
1252 KB |
Output is correct |
23 |
Correct |
380 ms |
22384 KB |
Output is correct |
24 |
Correct |
416 ms |
22560 KB |
Output is correct |
25 |
Correct |
487 ms |
43588 KB |
Output is correct |
26 |
Correct |
373 ms |
36488 KB |
Output is correct |
27 |
Correct |
309 ms |
1296 KB |
Output is correct |
28 |
Correct |
385 ms |
1072 KB |
Output is correct |
29 |
Correct |
318 ms |
1200 KB |
Output is correct |
30 |
Correct |
494 ms |
23956 KB |
Output is correct |
31 |
Correct |
298 ms |
1136 KB |
Output is correct |
32 |
Correct |
389 ms |
21112 KB |
Output is correct |
33 |
Correct |
277 ms |
1216 KB |
Output is correct |
34 |
Correct |
413 ms |
1240 KB |
Output is correct |
35 |
Correct |
349 ms |
1116 KB |
Output is correct |
36 |
Correct |
509 ms |
24968 KB |
Output is correct |
37 |
Correct |
478 ms |
24844 KB |
Output is correct |
38 |
Correct |
599 ms |
48904 KB |
Output is correct |
39 |
Correct |
561 ms |
44296 KB |
Output is correct |
40 |
Correct |
268 ms |
1240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
340 ms |
904 KB |
Execution killed with signal 13 |
2 |
Halted |
0 ms |
0 KB |
- |