Submission #831522

#	Time	Username	Problem	Language	Result	Execution time	Memory
831522		trs4630	Two Transportations (JOI19_transportations)	C++14	84 / 100	588 ms	49464 KiB

Azer

#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
using namespace std;
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;
	bool *visited;
	vpii *e;
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w=0;
	int relax_v;
	bool *buf;
	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((x&(1<<(bits-1-i)))? true: false);
		}
	}
	void Do(){
		while(t<n-1){
			if(mode==CL){
				mode=RE;
				if(leader){
					bool new_leader=(bool)(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,(int)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,(int)rec.second);
						relax_v=rec.second;
						Send(9,(int)rec.first);
						relax_w+=rec.first;
					}else{
						relax_v=Read(11);
						relax_w+=rec_other;
					}
				}else{
					if(winner){
						Send(11,(int)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){
	dis=(int *)malloc(sizeof(int)*MAXN);
	visited=(bool *)malloc(sizeof(bool)*MAXN);
	LOOP(i,MAXN){
		visited[i]=false;
	}
	e=(vpii *)malloc(sizeof(vpii)*MAXN);
	buf=(bool *)malloc(sizeof(bool)*58007);
	srand(200);
	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;
}

Baijan

#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
using namespace std;
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;
	bool *visited;
	vpii *e;
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w=0;
	int relax_v;
	bool *buf;
	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((x&(1<<(bits-1-i)))? true: false);
		}
	}
	void Do(){
		while(t<n-1){
			if(mode==CL){
				mode=RE;
				if(leader){
					bool new_leader=(bool)(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,(int)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,(int)rec.second);
						relax_v=rec.second;
						Send(9,(int)rec.first);
						relax_w+=rec.first;
					}else{
						relax_v=Read(11);
						relax_w+=rec_other;
					}
				}else{
					if(winner){
						Send(11,(int)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){
	dis=(int *)malloc(sizeof(int)*MAXN);
	visited=(bool *)malloc(sizeof(bool)*MAXN);
	LOOP(i,MAXN){
		visited[i]=false;
	}
	e=(vpii *)malloc(sizeof(vpii)*MAXN);
	buf=(bool *)malloc(sizeof(bool)*58007);
	srand(200);
	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();
	}
}

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