#include "Azer.h"
#include <stdlib.h>
#include <cassert>
#include <queue>
#define MAXN 2007
#define MAXM 500007
#define vi std::vector<int>
#define pii std::pair<int,int>
#define vpii std::vector<pii>
#define pqpii std::priority_queue<pii,vpii,std::greater<pii>>
#define LOOP(I,X) for(int I=0;I<X;I++)
#define pub push_back
namespace{
enum Mode{
CL, // choose leader
RE, // recommend edge
DW, // determine winner
SR, // send relax
RX // relax
};
Mode mode;
bool leader;
bool winner;
int n;
int dis[MAXN];
bool visited[MAXN]={};
vpii e[MAXN];
pqpii pq;
pii rec;
int rec_other;
int relax_w=0;
int relax_v;
bool buf[58007];
int buf_size=0;
int buf_now=0;
int t=0;
int bits_next;
int cnt=0;
int Read(int bits){
int ans=0;
LOOP(i,bits){
ans<<=1;
ans|=(int)buf[buf_now+i];
}
buf_now+=bits;
return ans;
}
void Send(int bits,int x){
LOOP(i,bits){
cnt++;
assert(buf_size+cnt<=58000);
SendA((bool)((x>>(bits-1-i))&1));
}
}
void Do(){
while(t<n-1){
if(mode==CL){
mode=RE;
if(leader){
bool new_leader=(bool)(std::rand()%2);
Send(1,(int)new_leader);
if(new_leader){
leader=!leader;
}
}else{
bool new_leader=(bool)Read(1);
if(new_leader){
leader=!leader;
}
}
if(leader){
bits_next=9;
return;
}
}
if(mode==RE){
mode=DW;
while(!pq.empty()){
pii x=pq.top();
if(!visited[x.second]){
break;
}
pq.pop();
}
if(pq.empty()){
rec={511,-1};
}else{
rec=pq.top();
rec.first-=relax_w;
}
if(leader){
rec_other=Read(9);
}else{
Send(9,rec.first);
bits_next=1;
return;
}
}
if(mode==DW){
mode=SR;
if(leader){
if(rec.first<=rec_other){
Send(1,1);
winner=true;
}else{
Send(1,0);
winner=false;
}
}else{
winner=!(bool)Read(1);
}
if(!winner){
if(leader){
bits_next=11;
}else{
bits_next=20;
}
return;
}
}
if(mode==SR){
mode=RX;
if(leader){
if(winner){
Send(11,rec.second);
relax_v=rec.second;
Send(9,rec.first);
relax_w+=rec.first;
}else{
relax_v=Read(11);
relax_w+=rec_other;
}
}else{
if(winner){
Send(11,rec.second);
relax_v=rec.second;
relax_w+=rec.first;
}else{
relax_v=Read(11);
relax_w+=Read(9);
}
}
}
if(mode==RX){
mode=CL;
dis[relax_v]=relax_w;
visited[relax_v]=true;
for(pii x:e[relax_v]){
if(!visited[x.first]){
pq.push({relax_w+x.second,x.first});
}
}
t++;
if(!leader){
bits_next=1;
return;
}
}
}
}
}
void InitA(int N,int A,vi U,vi V,vi C){
std::srand(49);
n=N;
LOOP(i,A){
e[U[i]].pub({V[i],C[i]});
e[V[i]].pub({U[i],C[i]});
}
dis[0]=0;
visited[0]=true;
for(pii x:e[0]){
pq.push({x.second,x.first});
}
mode=CL;
leader=true;
Do();
}
void ReceiveA(bool x){
buf[buf_size]=x;
buf_size++;
if(buf_size-buf_now==bits_next){
Do();
}
}
vi Answer(){
vi ans;
LOOP(i,n){
ans.pub(dis[i]);
}
return ans;
}
#include "Azer.h"
#include <stdlib.h>
#include <cassert>
#include <queue>
#define MAXN 2007
#define MAXM 500007
#define vi std::vector<int>
#define pii std::pair<int,int>
#define vpii std::vector<pii>
#define pqpii std::priority_queue<pii,vpii,std::greater<pii>>
#define LOOP(I,X) for(int I=0;I<X;I++)
#define pub push_back
namespace{
enum Mode{
CL, // choose leader
RE, // recommend edge
DW, // determine winner
SR, // send relax
RX // relax
};
Mode mode;
bool leader;
bool winner;
int n;
int dis[MAXN];
bool visited[MAXN]={};
vpii e[MAXN];
pqpii pq;
pii rec;
int rec_other;
int relax_w=0;
int relax_v;
bool buf[58007];
int buf_size=0;
int buf_now=0;
int t=0;
int bits_next;
int cnt=0;
int Read(int bits){
int ans=0;
LOOP(i,bits){
ans<<=1;
ans|=(int)buf[buf_now+i];
}
buf_now+=bits;
return ans;
}
void Send(int bits,int x){
LOOP(i,bits){
cnt++;
assert(buf_size+cnt<=58000);
SendA((bool)((x>>(bits-1-i))&1));
}
}
void Do(){
while(t<n-1){
if(mode==CL){
mode=RE;
if(leader){
bool new_leader=(bool)(std::rand()%2);
Send(1,(int)new_leader);
if(new_leader){
leader=!leader;
}
}else{
bool new_leader=(bool)Read(1);
if(new_leader){
leader=!leader;
}
}
if(leader){
bits_next=9;
return;
}
}
if(mode==RE){
mode=DW;
while(!pq.empty()){
pii x=pq.top();
if(!visited[x.second]){
break;
}
pq.pop();
}
if(pq.empty()){
rec={511,-1};
}else{
rec=pq.top();
rec.first-=relax_w;
}
if(leader){
rec_other=Read(9);
}else{
Send(9,rec.first);
bits_next=1;
return;
}
}
if(mode==DW){
mode=SR;
if(leader){
if(rec.first<=rec_other){
Send(1,1);
winner=true;
}else{
Send(1,0);
winner=false;
}
}else{
winner=!(bool)Read(1);
}
if(!winner){
if(leader){
bits_next=11;
}else{
bits_next=20;
}
return;
}
}
if(mode==SR){
mode=RX;
if(leader){
if(winner){
Send(11,rec.second);
relax_v=rec.second;
Send(9,rec.first);
relax_w+=rec.first;
}else{
relax_v=Read(11);
relax_w+=rec_other;
}
}else{
if(winner){
Send(11,rec.second);
relax_v=rec.second;
relax_w+=rec.first;
}else{
relax_v=Read(11);
relax_w+=Read(9);
}
}
}
if(mode==RX){
mode=CL;
dis[relax_v]=relax_w;
visited[relax_v]=true;
for(pii x:e[relax_v]){
if(!visited[x.first]){
pq.push({relax_w+x.second,x.first});
}
}
t++;
if(!leader){
bits_next=1;
return;
}
}
}
}
}
void InitA(int N,int A,vi U,vi V,vi C){
std::srand(49);
n=N;
LOOP(i,A){
e[U[i]].pub({V[i],C[i]});
e[V[i]].pub({U[i],C[i]});
}
dis[0]=0;
visited[0]=true;
for(pii x:e[0]){
pq.push({x.second,x.first});
}
mode=CL;
leader=true;
Do();
}
void ReceiveA(bool x){
buf[buf_size]=x;
buf_size++;
if(buf_size-buf_now==bits_next){
Do();
}
}
vi Answer(){
vi ans;
LOOP(i,n){
ans.pub(dis[i]);
}
return ans;
}
#include "Baijan.h"
#include <stdlib.h>
#include <cassert>
#include <queue>
#define MAXN 2007
#define MAXM 500007
#define vi std::vector<int>
#define pii std::pair<int,int>
#define vpii std::vector<pii>
#define pqpii std::priority_queue<pii,vpii,std::greater<pii>>
#define LOOP(I,X) for(int I=0;I<X;I++)
#define pub push_back
namespace{
enum Mode{
CL, // choose leader
RE, // recommend edge
DW, // determine winner
SR, // send relax
RX // relax
};
Mode mode;
bool leader;
bool winner;
int n;
int dis[MAXN];
bool visited[MAXN]={};
vpii e[MAXN];
pqpii pq;
pii rec;
int rec_other;
int relax_w=0;
int relax_v;
bool buf[58007];
int buf_size=0;
int buf_now=0;
int t=0;
int bits_next;
int cnt=0;
int Read(int bits){
int ans=0;
LOOP(i,bits){
ans<<=1;
ans|=(int)buf[buf_now+i];
}
buf_now+=bits;
return ans;
}
void Send(int bits,int x){
LOOP(i,bits){
cnt++;
assert(buf_size+cnt<=58000);
SendB((bool)((x>>(bits-1-i))&1));
}
}
void Do(){
while(t<n-1){
if(mode==CL){
mode=RE;
if(leader){
bool new_leader=(bool)(std::rand()%2);
Send(1,(int)new_leader);
if(new_leader){
leader=!leader;
}
}else{
bool new_leader=(bool)Read(1);
if(new_leader){
leader=!leader;
}
}
if(leader){
bits_next=9;
return;
}
}
if(mode==RE){
mode=DW;
while(!pq.empty()){
pii x=pq.top();
if(!visited[x.second]){
break;
}
pq.pop();
}
if(pq.empty()){
rec={511,-1};
}else{
rec=pq.top();
rec.first-=relax_w;
}
if(leader){
rec_other=Read(9);
}else{
Send(9,rec.first);
bits_next=1;
return;
}
}
if(mode==DW){
mode=SR;
if(leader){
if(rec.first<=rec_other){
Send(1,1);
winner=true;
}else{
Send(1,0);
winner=false;
}
}else{
winner=!(bool)Read(1);
}
if(!winner){
if(leader){
bits_next=11;
}else{
bits_next=20;
}
return;
}
}
if(mode==SR){
mode=RX;
if(leader){
if(winner){
Send(11,rec.second);
relax_v=rec.second;
Send(9,rec.first);
relax_w+=rec.first;
}else{
relax_v=Read(11);
relax_w+=rec_other;
}
}else{
if(winner){
Send(11,rec.second);
relax_v=rec.second;
relax_w+=rec.first;
}else{
relax_v=Read(11);
relax_w+=Read(9);
}
}
}
if(mode==RX){
mode=CL;
dis[relax_v]=relax_w;
visited[relax_v]=true;
for(pii x:e[relax_v]){
if(!visited[x.first]){
pq.push({relax_w+x.second,x.first});
}
}
t++;
if(!leader){
bits_next=1;
return;
}
}
}
}
}
void InitB(int N,int A,vi U,vi V,vi C){
std::srand(49);
n=N;
LOOP(i,A){
e[U[i]].pub({V[i],C[i]});
e[V[i]].pub({U[i],C[i]});
}
dis[0]=0;
visited[0]=true;
for(pii x:e[0]){
pq.push({x.second,x.first});
}
mode=CL;
leader=false;
bits_next=1;
}
void ReceiveB(bool x){
buf[buf_size]=x;
buf_size++;
if(buf_size-buf_now==bits_next){
Do();
}
}
Compilation message
Azer.cpp:205:7: error: multiple definition of 'enum {anonymous}::Mode'
205 | enum Mode{
| ^~~~
Azer.cpp:14:7: note: previous definition here
14 | enum Mode{
| ^~~~
Azer.cpp:212:7: error: redefinition of '{anonymous}::Mode {anonymous}::mode'
212 | Mode mode;
| ^~~~
Azer.cpp:21:7: note: '{anonymous}::Mode {anonymous}::mode' previously declared here
21 | Mode mode;
| ^~~~
Azer.cpp:213:7: error: redefinition of 'bool {anonymous}::leader'
213 | bool leader;
| ^~~~~~
Azer.cpp:22:7: note: 'bool {anonymous}::leader' previously declared here
22 | bool leader;
| ^~~~~~
Azer.cpp:214:7: error: redefinition of 'bool {anonymous}::winner'
214 | bool winner;
| ^~~~~~
Azer.cpp:23:7: note: 'bool {anonymous}::winner' previously declared here
23 | bool winner;
| ^~~~~~
Azer.cpp:215:6: error: redefinition of 'int {anonymous}::n'
215 | int n;
| ^
Azer.cpp:24:6: note: 'int {anonymous}::n' previously declared here
24 | int n;
| ^
Azer.cpp:216:6: error: redefinition of 'int {anonymous}::dis [2007]'
216 | int dis[MAXN];
| ^~~
Azer.cpp:25:6: note: 'int {anonymous}::dis [2007]' previously declared here
25 | int dis[MAXN];
| ^~~
Azer.cpp:217:7: error: redefinition of 'bool {anonymous}::visited [2007]'
217 | bool visited[MAXN]={};
| ^~~~~~~
Azer.cpp:26:7: note: 'bool {anonymous}::visited [2007]' previously defined here
26 | bool visited[MAXN]={};
| ^~~~~~~
Azer.cpp:218:7: error: redefinition of 'std::vector<std::pair<int, int> > {anonymous}::e [2007]'
218 | vpii e[MAXN];
| ^
Azer.cpp:27:7: note: 'std::vector<std::pair<int, int> > {anonymous}::e [2007]' previously declared here
27 | vpii e[MAXN];
| ^
Azer.cpp:219:8: error: redefinition of 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > {anonymous}::pq'
219 | pqpii pq;
| ^~
Azer.cpp:28:8: note: 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > {anonymous}::pq' previously declared here
28 | pqpii pq;
| ^~
Azer.cpp:220:6: error: redefinition of 'std::pair<int, int> {anonymous}::rec'
220 | pii rec;
| ^~~
Azer.cpp:29:6: note: 'std::pair<int, int> {anonymous}::rec' previously defined here
29 | pii rec;
| ^~~
Azer.cpp:221:6: error: redefinition of 'int {anonymous}::rec_other'
221 | int rec_other;
| ^~~~~~~~~
Azer.cpp:30:6: note: 'int {anonymous}::rec_other' previously declared here
30 | int rec_other;
| ^~~~~~~~~
Azer.cpp:222:6: error: redefinition of 'int {anonymous}::relax_w'
222 | int relax_w=0;
| ^~~~~~~
Azer.cpp:31:6: note: 'int {anonymous}::relax_w' previously defined here
31 | int relax_w=0;
| ^~~~~~~
Azer.cpp:223:6: error: redefinition of 'int {anonymous}::relax_v'
223 | int relax_v;
| ^~~~~~~
Azer.cpp:32:6: note: 'int {anonymous}::relax_v' previously declared here
32 | int relax_v;
| ^~~~~~~
Azer.cpp:224:7: error: redefinition of 'bool {anonymous}::buf [58007]'
224 | bool buf[58007];
| ^~~
Azer.cpp:33:7: note: 'bool {anonymous}::buf [58007]' previously declared here
33 | bool buf[58007];
| ^~~
Azer.cpp:225:6: error: redefinition of 'int {anonymous}::buf_size'
225 | int buf_size=0;
| ^~~~~~~~
Azer.cpp:34:6: note: 'int {anonymous}::buf_size' previously defined here
34 | int buf_size=0;
| ^~~~~~~~
Azer.cpp:226:6: error: redefinition of 'int {anonymous}::buf_now'
226 | int buf_now=0;
| ^~~~~~~
Azer.cpp:35:6: note: 'int {anonymous}::buf_now' previously defined here
35 | int buf_now=0;
| ^~~~~~~
Azer.cpp:227:6: error: redefinition of 'int {anonymous}::t'
227 | int t=0;
| ^
Azer.cpp:36:6: note: 'int {anonymous}::t' previously defined here
36 | int t=0;
| ^
Azer.cpp:228:6: error: redefinition of 'int {anonymous}::bits_next'
228 | int bits_next;
| ^~~~~~~~~
Azer.cpp:37:6: note: 'int {anonymous}::bits_next' previously declared here
37 | int bits_next;
| ^~~~~~~~~
Azer.cpp:229:5: error: redefinition of 'int {anonymous}::cnt'
229 | int cnt=0;
| ^~~
Azer.cpp:38:5: note: 'int {anonymous}::cnt' previously defined here
38 | int cnt=0;
| ^~~
Azer.cpp:230:6: error: redefinition of 'int {anonymous}::Read(int)'
230 | int Read(int bits){
| ^~~~
Azer.cpp:39:6: note: 'int {anonymous}::Read(int)' previously defined here
39 | int Read(int bits){
| ^~~~
Azer.cpp:239:7: error: redefinition of 'void {anonymous}::Send(int, int)'
239 | void Send(int bits,int x){
| ^~~~
Azer.cpp:48:7: note: 'void {anonymous}::Send(int, int)' previously defined here
48 | void Send(int bits,int x){
| ^~~~
Azer.cpp:246:7: error: redefinition of 'void {anonymous}::Do()'
246 | void Do(){
| ^~
Azer.cpp:55:7: note: 'void {anonymous}::Do()' previously defined here
55 | void Do(){
| ^~
Azer.cpp:353:6: error: redefinition of 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)'
353 | void InitA(int N,int A,vi U,vi V,vi C){
| ^~~~~
Azer.cpp:162:6: note: 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
162 | void InitA(int N,int A,vi U,vi V,vi C){
| ^~~~~
Azer.cpp:369:6: error: redefinition of 'void ReceiveA(bool)'
369 | void ReceiveA(bool x){
| ^~~~~~~~
Azer.cpp:178:6: note: 'void ReceiveA(bool)' previously defined here
178 | void ReceiveA(bool x){
| ^~~~~~~~
Azer.cpp:376:4: error: redefinition of 'std::vector<int> Answer()'
376 | vi Answer(){
| ^~~~~~
Azer.cpp:185:4: note: 'std::vector<int> Answer()' previously defined here
185 | vi Answer(){
| ^~~~~~
Azer.cpp:246:7: warning: 'void {anonymous}::Do()' defined but not used [-Wunused-function]
246 | void Do(){
| ^~
Azer.cpp:239:7: warning: 'void {anonymous}::Send(int, int)' defined but not used [-Wunused-function]
239 | void Send(int bits,int x){
| ^~~~
Azer.cpp:230:6: warning: 'int {anonymous}::Read(int)' defined but not used [-Wunused-function]
230 | int Read(int bits){
| ^~~~
