#include "Azer.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <iostream>
using namespace std;
namespace {
int const nmax = 2000;
int const inf = nmax * 500;
int const cost_size = 9;
int const id_size = 11;
int global = 0;
vector<pair<int,int>> g[1 + nmax];
int n;
int dist[1 + nmax], forever[1 + nmax];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
}
namespace rec{
int _count = 0;
int wait;
int curr;
vector<int> history;
void waitfor(int _wait){
wait = _wait;
_count = 0;
curr = 0;
}
}
void refresh(){
while(0 < pq.size()){
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
if(cost == dist[node]){
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
int edge = g[node][h].second;
if(dist[node] + edge < dist[to]){
dist[to] = dist[node] + edge;
pq.push({dist[to], to});
}
}
}
}
}
int best(){
int result = -1;
for(int i = 0;i < n; i++)
if(forever[i] == 0)
if(result == -1 || dist[i] < dist[result])
result = i;
return result;
}
void sendnumber(int val, int bits){
if((1 << bits) <= val)
val = (1 << bits) - 1;
for(int i = 0; i < bits; i++)
SendA(0 < (val & (1 << i)));
}
void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> cost) {
::n = n;
for(int i = 0; i < m; i++){
g[u[i]].push_back({v[i], cost[i]});
g[v[i]].push_back({u[i], cost[i]});
}
for(int i = 0;i < n; i++)
dist[i] = inf;
dist[0] = 0;
pq.push({0, 0});
refresh();
sendnumber(dist[best()] - global, cost_size);
rec::waitfor(cost_size);
}
void ReceiveNumber(int number, int bits){
if(bits == cost_size){
int id = best();
int mine = dist[id] - global;
if(mine <= number) {
sendnumber(id, id_size);
global += mine;
forever[id] = 1;
if(best() != -1) {
sendnumber(dist[best()] - global, cost_size);
rec::waitfor(cost_size);
}
} else
rec::waitfor(id_size);
} else {
dist[number] = global + rec::history.back();
pq.push({dist[number], number});
forever[number] = 1;
refresh();
global += rec::history.back();
if(best() != -1) {
sendnumber(dist[best()] - global, cost_size);
rec::waitfor(cost_size);
}
}
rec::history.push_back(number);
}
void ReceiveA(bool x) {
rec::curr |= (x<<rec::_count);
rec::_count++;
if(rec::wait == rec::_count)
ReceiveNumber(rec::curr, rec::wait);
}
vector<int> Answer() {
vector<int> ans(n);
for (int k = 0; k < n; ++k)
ans[k] = dist[k];
return ans;
}
#include "Baijan.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
namespace {
int const nmax = 2000;
int const inf = nmax * 500;
int const cost_size = 9;
int const id_size = 11;
int global = 0;
vector<pair<int,int>> g[1 + nmax];
int n;
int dist[1 + nmax], forever[1 + nmax];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
}
namespace req{
int _count = 0;
int wait;
int curr;
vector<int> history;
void waitfor(int _wait){
wait = _wait;
_count = 0;
curr = 0;
}
}
void refreshB(){
while(0 < pq.size()){
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
if(cost == dist[node]){
for(int h = 0; h < g[node].size(); h++){
int to = g[node][h].first;
int edge = g[node][h].second;
if(dist[node] + edge < dist[to]){
dist[to] = dist[node] + edge;
pq.push({dist[to], to});
}
}
}
}
}
int bestB(){
int result = -1;
for(int i = 0;i < n; i++)
if(forever[i] == 0)
if(result == -1 || dist[i] < dist[result])
result = i;
return result;
}
void sendnumberB(int val, int bits){
if((1 << bits) <= val)
val = (1 << bits) - 1;
for(int i = 0; i < bits; i++)
SendB(0 < (val & (1 << i)));
}
void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> cost) {
::n = n;
for(int i = 0; i < m; i++){
g[u[i]].push_back({v[i], cost[i]});
g[v[i]].push_back({u[i], cost[i]});
}
for(int i = 0;i < n; i++)
dist[i] = inf;
dist[0] = 0;
pq.push({0, 0});
refreshB();
req::waitfor(cost_size);
}
void ReceiveNumberB(int number, int bits){
if(bits == cost_size){
int id = bestB();
int mine = dist[id] - global;
sendnumberB(mine, cost_size);
if(mine < number) {
sendnumberB(id, id_size);
global += mine;
forever[id] = 1;
req::waitfor(cost_size);
} else
req::waitfor(id_size);
} else {
dist[number] = global + req::history.back();
pq.push({dist[number], number});
forever[number] = 1;
refreshB();
global += req::history.back();
req::waitfor(cost_size);
}
req::history.push_back(number);
}
void ReceiveB(bool x) {
req::curr |= (x<<req::_count);
req::_count++;
if(req::wait == req::_count)
ReceiveNumberB(req::curr, req::wait);
}
Compilation message
Azer.cpp: In function 'void refresh()':
Azer.cpp:42:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
Baijan.cpp: In function 'void refreshB()':
Baijan.cpp:39:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int h = 0; h < g[node].size(); h++){
~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
944 ms |
1864 KB |
Output is correct |
2 |
Correct |
18 ms |
1536 KB |
Output is correct |
3 |
Correct |
1010 ms |
2272 KB |
Output is correct |
4 |
Correct |
1190 ms |
20528 KB |
Output is correct |
5 |
Correct |
68 ms |
2048 KB |
Output is correct |
6 |
Correct |
976 ms |
5376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
1536 KB |
Output is correct |
2 |
Correct |
994 ms |
2368 KB |
Output is correct |
3 |
Correct |
1092 ms |
2016 KB |
Output is correct |
4 |
Correct |
1419 ms |
55264 KB |
Output is correct |
5 |
Correct |
1426 ms |
48608 KB |
Output is correct |
6 |
Correct |
210 ms |
1536 KB |
Output is correct |
7 |
Correct |
1438 ms |
48792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1018 ms |
2112 KB |
Output is correct |
2 |
Correct |
18 ms |
1280 KB |
Output is correct |
3 |
Correct |
988 ms |
1856 KB |
Output is correct |
4 |
Correct |
1072 ms |
2272 KB |
Output is correct |
5 |
Correct |
1020 ms |
2024 KB |
Output is correct |
6 |
Correct |
980 ms |
2272 KB |
Output is correct |
7 |
Correct |
848 ms |
1768 KB |
Output is correct |
8 |
Correct |
1056 ms |
2272 KB |
Output is correct |
9 |
Correct |
1020 ms |
1792 KB |
Output is correct |
10 |
Correct |
1030 ms |
2528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
446 ms |
1728 KB |
Output is correct |
2 |
Correct |
404 ms |
1672 KB |
Output is correct |
3 |
Correct |
666 ms |
23992 KB |
Output is correct |
4 |
Correct |
458 ms |
2304 KB |
Output is correct |
5 |
Correct |
658 ms |
17456 KB |
Output is correct |
6 |
Correct |
440 ms |
1760 KB |
Output is correct |
7 |
Correct |
476 ms |
2016 KB |
Output is correct |
8 |
Correct |
440 ms |
2016 KB |
Output is correct |
9 |
Correct |
754 ms |
36320 KB |
Output is correct |
10 |
Correct |
813 ms |
36320 KB |
Output is correct |
11 |
Correct |
1118 ms |
61608 KB |
Output is correct |
12 |
Correct |
862 ms |
54048 KB |
Output is correct |
13 |
Correct |
462 ms |
1792 KB |
Output is correct |
14 |
Correct |
18 ms |
1536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
446 ms |
1728 KB |
Output is correct |
2 |
Correct |
404 ms |
1672 KB |
Output is correct |
3 |
Correct |
666 ms |
23992 KB |
Output is correct |
4 |
Correct |
458 ms |
2304 KB |
Output is correct |
5 |
Correct |
658 ms |
17456 KB |
Output is correct |
6 |
Correct |
440 ms |
1760 KB |
Output is correct |
7 |
Correct |
476 ms |
2016 KB |
Output is correct |
8 |
Correct |
440 ms |
2016 KB |
Output is correct |
9 |
Correct |
754 ms |
36320 KB |
Output is correct |
10 |
Correct |
813 ms |
36320 KB |
Output is correct |
11 |
Correct |
1118 ms |
61608 KB |
Output is correct |
12 |
Correct |
862 ms |
54048 KB |
Output is correct |
13 |
Correct |
462 ms |
1792 KB |
Output is correct |
14 |
Correct |
18 ms |
1536 KB |
Output is correct |
15 |
Correct |
538 ms |
1536 KB |
Output is correct |
16 |
Correct |
570 ms |
1792 KB |
Output is correct |
17 |
Correct |
532 ms |
1800 KB |
Output is correct |
18 |
Correct |
702 ms |
17720 KB |
Output is correct |
19 |
Correct |
614 ms |
1792 KB |
Output is correct |
20 |
Correct |
794 ms |
18432 KB |
Output is correct |
21 |
Correct |
570 ms |
1792 KB |
Output is correct |
22 |
Correct |
558 ms |
1792 KB |
Output is correct |
23 |
Correct |
850 ms |
44456 KB |
Output is correct |
24 |
Correct |
938 ms |
44192 KB |
Output is correct |
25 |
Correct |
1352 ms |
75536 KB |
Output is correct |
26 |
Correct |
1102 ms |
64704 KB |
Output is correct |
27 |
Correct |
528 ms |
2048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
446 ms |
1728 KB |
Output is correct |
2 |
Correct |
404 ms |
1672 KB |
Output is correct |
3 |
Correct |
666 ms |
23992 KB |
Output is correct |
4 |
Correct |
458 ms |
2304 KB |
Output is correct |
5 |
Correct |
658 ms |
17456 KB |
Output is correct |
6 |
Correct |
440 ms |
1760 KB |
Output is correct |
7 |
Correct |
476 ms |
2016 KB |
Output is correct |
8 |
Correct |
440 ms |
2016 KB |
Output is correct |
9 |
Correct |
754 ms |
36320 KB |
Output is correct |
10 |
Correct |
813 ms |
36320 KB |
Output is correct |
11 |
Correct |
1118 ms |
61608 KB |
Output is correct |
12 |
Correct |
862 ms |
54048 KB |
Output is correct |
13 |
Correct |
462 ms |
1792 KB |
Output is correct |
14 |
Correct |
18 ms |
1536 KB |
Output is correct |
15 |
Correct |
538 ms |
1536 KB |
Output is correct |
16 |
Correct |
570 ms |
1792 KB |
Output is correct |
17 |
Correct |
532 ms |
1800 KB |
Output is correct |
18 |
Correct |
702 ms |
17720 KB |
Output is correct |
19 |
Correct |
614 ms |
1792 KB |
Output is correct |
20 |
Correct |
794 ms |
18432 KB |
Output is correct |
21 |
Correct |
570 ms |
1792 KB |
Output is correct |
22 |
Correct |
558 ms |
1792 KB |
Output is correct |
23 |
Correct |
850 ms |
44456 KB |
Output is correct |
24 |
Correct |
938 ms |
44192 KB |
Output is correct |
25 |
Correct |
1352 ms |
75536 KB |
Output is correct |
26 |
Correct |
1102 ms |
64704 KB |
Output is correct |
27 |
Correct |
528 ms |
2048 KB |
Output is correct |
28 |
Correct |
660 ms |
2288 KB |
Output is correct |
29 |
Correct |
702 ms |
2016 KB |
Output is correct |
30 |
Correct |
1124 ms |
42208 KB |
Output is correct |
31 |
Correct |
686 ms |
1792 KB |
Output is correct |
32 |
Correct |
1032 ms |
37744 KB |
Output is correct |
33 |
Correct |
802 ms |
2016 KB |
Output is correct |
34 |
Correct |
684 ms |
2272 KB |
Output is correct |
35 |
Correct |
704 ms |
2272 KB |
Output is correct |
36 |
Correct |
1100 ms |
49744 KB |
Output is correct |
37 |
Correct |
1148 ms |
49888 KB |
Output is correct |
38 |
Correct |
1545 ms |
85944 KB |
Output is correct |
39 |
Correct |
1406 ms |
79048 KB |
Output is correct |
40 |
Correct |
704 ms |
2272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
944 ms |
1864 KB |
Output is correct |
2 |
Correct |
18 ms |
1536 KB |
Output is correct |
3 |
Correct |
1010 ms |
2272 KB |
Output is correct |
4 |
Correct |
1190 ms |
20528 KB |
Output is correct |
5 |
Correct |
68 ms |
2048 KB |
Output is correct |
6 |
Correct |
976 ms |
5376 KB |
Output is correct |
7 |
Correct |
16 ms |
1536 KB |
Output is correct |
8 |
Correct |
994 ms |
2368 KB |
Output is correct |
9 |
Correct |
1092 ms |
2016 KB |
Output is correct |
10 |
Correct |
1419 ms |
55264 KB |
Output is correct |
11 |
Correct |
1426 ms |
48608 KB |
Output is correct |
12 |
Correct |
210 ms |
1536 KB |
Output is correct |
13 |
Correct |
1438 ms |
48792 KB |
Output is correct |
14 |
Correct |
1018 ms |
2112 KB |
Output is correct |
15 |
Correct |
18 ms |
1280 KB |
Output is correct |
16 |
Correct |
988 ms |
1856 KB |
Output is correct |
17 |
Correct |
1072 ms |
2272 KB |
Output is correct |
18 |
Correct |
1020 ms |
2024 KB |
Output is correct |
19 |
Correct |
980 ms |
2272 KB |
Output is correct |
20 |
Correct |
848 ms |
1768 KB |
Output is correct |
21 |
Correct |
1056 ms |
2272 KB |
Output is correct |
22 |
Correct |
1020 ms |
1792 KB |
Output is correct |
23 |
Correct |
1030 ms |
2528 KB |
Output is correct |
24 |
Correct |
446 ms |
1728 KB |
Output is correct |
25 |
Correct |
404 ms |
1672 KB |
Output is correct |
26 |
Correct |
666 ms |
23992 KB |
Output is correct |
27 |
Correct |
458 ms |
2304 KB |
Output is correct |
28 |
Correct |
658 ms |
17456 KB |
Output is correct |
29 |
Correct |
440 ms |
1760 KB |
Output is correct |
30 |
Correct |
476 ms |
2016 KB |
Output is correct |
31 |
Correct |
440 ms |
2016 KB |
Output is correct |
32 |
Correct |
754 ms |
36320 KB |
Output is correct |
33 |
Correct |
813 ms |
36320 KB |
Output is correct |
34 |
Correct |
1118 ms |
61608 KB |
Output is correct |
35 |
Correct |
862 ms |
54048 KB |
Output is correct |
36 |
Correct |
462 ms |
1792 KB |
Output is correct |
37 |
Correct |
18 ms |
1536 KB |
Output is correct |
38 |
Correct |
538 ms |
1536 KB |
Output is correct |
39 |
Correct |
570 ms |
1792 KB |
Output is correct |
40 |
Correct |
532 ms |
1800 KB |
Output is correct |
41 |
Correct |
702 ms |
17720 KB |
Output is correct |
42 |
Correct |
614 ms |
1792 KB |
Output is correct |
43 |
Correct |
794 ms |
18432 KB |
Output is correct |
44 |
Correct |
570 ms |
1792 KB |
Output is correct |
45 |
Correct |
558 ms |
1792 KB |
Output is correct |
46 |
Correct |
850 ms |
44456 KB |
Output is correct |
47 |
Correct |
938 ms |
44192 KB |
Output is correct |
48 |
Correct |
1352 ms |
75536 KB |
Output is correct |
49 |
Correct |
1102 ms |
64704 KB |
Output is correct |
50 |
Correct |
528 ms |
2048 KB |
Output is correct |
51 |
Correct |
660 ms |
2288 KB |
Output is correct |
52 |
Correct |
702 ms |
2016 KB |
Output is correct |
53 |
Correct |
1124 ms |
42208 KB |
Output is correct |
54 |
Correct |
686 ms |
1792 KB |
Output is correct |
55 |
Correct |
1032 ms |
37744 KB |
Output is correct |
56 |
Correct |
802 ms |
2016 KB |
Output is correct |
57 |
Correct |
684 ms |
2272 KB |
Output is correct |
58 |
Correct |
704 ms |
2272 KB |
Output is correct |
59 |
Correct |
1100 ms |
49744 KB |
Output is correct |
60 |
Correct |
1148 ms |
49888 KB |
Output is correct |
61 |
Correct |
1545 ms |
85944 KB |
Output is correct |
62 |
Correct |
1406 ms |
79048 KB |
Output is correct |
63 |
Correct |
704 ms |
2272 KB |
Output is correct |
64 |
Correct |
1158 ms |
2080 KB |
Output is correct |
65 |
Correct |
1472 ms |
47328 KB |
Output is correct |
66 |
Correct |
1447 ms |
41136 KB |
Output is correct |
67 |
Correct |
992 ms |
2048 KB |
Output is correct |
68 |
Correct |
1030 ms |
2272 KB |
Output is correct |
69 |
Correct |
1814 ms |
84024 KB |
Output is correct |
70 |
Correct |
1790 ms |
69056 KB |
Output is correct |
71 |
Correct |
1058 ms |
9664 KB |
Output is correct |
72 |
Correct |
1050 ms |
2560 KB |
Output is correct |