Submission #826215

#	Time	Username	Problem	Language	Result	Execution time	Memory
826215		NoName14159	Two Transportations (JOI19_transportations)	C++17	0 / 100	112 ms	460 KiB

Azer

#include "Azer.h"
#include <stdlib.h>
#include <queue>
#define MAXN 2000
#define MAXM 500000
#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,m;
	int dis[MAXN];
	bool visited[MAXN]={};
	vpii e[MAXN];
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w;
	int relax_v;
	bool buf[11];
	int buf_size;
	bool ready;
	int Read(int bits){
		while(buf_size<bits){
		}
		buf_size=0;
		int ans=0;
		LOOP(i,bits){
			ans<<=1;
			ans|=buf[i];
		}
		return ans;
	}
	void Send(int bits,int x){
		LOOP(i,bits){
			SendA((bool)((x>>(bits-1-i))&1));
		}
	}
	void Do(){
		LOOP(t,n-1){
			if(mode==CL){
				if(leader){
					bool new_leader=(bool)rand()%2;
					Send(1,(int)new_leader);
					if(new_leader){
						leader=!leader;
					}
				}else{
					Read(1);
					if(buf[0]){
						leader=!leader;
					}
				}
				mode=RE;
			}
			if(mode==RE){
				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);
				}
				mode=DW;
			}
			if(mode==DW){
				if(leader){
					if(rec.first<=rec_other){
						Send(1,1);
						winner=true;
					}else{
						Send(1,0);
						winner=false;
					}
				}else{
					winner=!(bool)Read(1);
				}
				mode=SR;
			}
			if(mode==SR){
				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);
					}
				}
				mode=RX;
			}
			if(mode==RX){
				dis[relax_v]=relax_w;
				visited[relax_v]=true;
				for(pii x:e[relax_v]){
					if(!visited[x.second]){
						pq.push({relax_w+x.second,x.first});
					}
				}
				mode=CL;
			}
		}
		ready=true;
	}
}
void InitA(int N,int A,vi U,vi V,vi C){
	srand(49);
	n=N;
	LOOP(i,A){
		e[U[i]].pub({V[i],C[i]});
	}
	dis[0]=0;
	visited[0]=true;
	for(pii x:e[0]){
		pq.push(x);
	}
	ready=false;
	mode=CL;
	leader=true;
	Do();
}
void ReceiveA(bool x){
	buf[buf_size]=x;
	buf_size++;
}
vi Answer(){
	while(!ready){
	}
	vi ans;
	LOOP(i,n){
		ans.pub(dis[i]);
	}
	return ans;
}

Baijan

#include "Baijan.h"
#include <stdlib.h>
#include <queue>
#define MAXN 2000
#define MAXM 500000
#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,m;
	int dis[MAXN];
	bool visited[MAXN]={};
	vpii e[MAXN];
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w;
	int relax_v;
	bool buf[11];
	int buf_size;
	int Read(int bits){
		while(buf_size<bits){
		}
		buf_size=0;
		int ans=0;
		LOOP(i,bits){
			ans<<=1;
			ans|=buf[i];
		}
		return ans;
	}
	void Send(int bits,int x){
		LOOP(i,bits){
			SendB((bool)((x>>(bits-1-i))&1));
		}
	}
	void Do(){
		LOOP(t,n-1){
			if(mode==CL){
				if(leader){
					bool new_leader=(bool)rand()%2;
					Send(1,(int)new_leader);
					if(new_leader){
						leader=!leader;
					}
				}else{
					Read(1);
					if(buf[0]){
						leader=!leader;
					}
				}
				mode=RE;
			}
			if(mode==RE){
				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);
				}
				mode=DW;
			}
			if(mode==DW){
				if(leader){
					if(rec.first<=rec_other){
						Send(1,1);
						winner=true;
					}else{
						Send(1,0);
						winner=false;
					}
				}else{
					winner=!(bool)Read(1);
				}
				mode=SR;
			}
			if(mode==SR){
				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);
					}
				}
				mode=RX;
			}
			if(mode==RX){
				dis[relax_v]=relax_w;
				visited[relax_v]=true;
				for(pii x:e[relax_v]){
					if(!visited[x.second]){
						pq.push({relax_w+x.second,x.first});
					}
				}
				mode=CL;
			}
		}
	}
}
void InitB(int N,int B,vi U,vi V,vi C){
	srand(49);
	n=N;
	LOOP(i,B){
		e[U[i]].pub({V[i],C[i]});
	}
	dis[0]=0;
	visited[0]=true;
	for(pii x:e[0]){
		pq.push(x);
	}
	mode=CL;
	leader=false;
	Do();
}
void ReceiveB(bool x){
	buf[buf_size]=x;
	buf_size++;
}

Compilation message (stderr)

Azer.cpp:23:8: warning: '{anonymous}::m' defined but not used [-Wunused-variable]
   23 |  int n,m;
      |        ^

Baijan.cpp:23:8: warning: '{anonymous}::m' defined but not used [-Wunused-variable]
   23 |  int n,m;
      |        ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16