oj.uz

답안 #826467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
826467 2023-08-15T15:37:46 Z NoName14159 Two Transportations (JOI19_transportations) C++17
0 / 100
 4 ms 656 KB 
#include "Azer.h"
#include <stdlib.h>
#include <iostream>
#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;
	int dis[MAXN];
	bool visited[MAXN]={};
	vpii e[MAXN];
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w;
	int relax_v;
	bool buf[58000];
	int buf_size=0;
	int buf_now=0;
	bool ready;
	int Read(int bits){
		while(buf_size-buf_now<bits){
		}
		int ans=0;
		LOOP(i,bits){
			ans<<=1;
			ans|=(int)buf[buf_now+i];
		}
		buf_now+=bits;
//std::cout<<bits<<" "<<ans<<" read\n";
		return ans;
	}
	void Send(int bits,int x){
//std::cout<<bits<<" "<<x<<" send\n";
		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.first]){
						pq.push({relax_w+x.second,x.first});
					}
				}
				mode=CL;
			}
//std::cout<<relax_v<<" "<<relax_w<<"\n";
		}
		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]});
		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});
	}
	ready=false;
	mode=CL;
	leader=true;
	Do();
}
void ReceiveA(bool x){
//std::cout<<x<<" receive\n";
	buf[buf_size]=x;
	buf_size++;
}
vi Answer(){
	while(!ready){
	}
	vi ans;
	LOOP(i,n){
		ans.pub(dis[i]);
	}
	return ans;
}

#include "Baijan.h"
#include <stdlib.h>
#include <iostream>
#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;
	int dis[MAXN];
	bool visited[MAXN]={};
	vpii e[MAXN];
	pqpii pq;
	pii rec;
	int rec_other;
	int relax_w;
	int relax_v;
	bool buf[58000];
	int buf_size=0;
	int buf_now=0;
	int Read(int bits){
		while(buf_size-buf_now<bits){
		}
		int ans=0;
		LOOP(i,bits){
			ans<<=1;
			ans|=(int)buf[buf_now+i];
		}
		buf_now+=bits;
//std::cout<<bits<<" "<<ans<<" read\n";
		return ans;
	}
	void Send(int bits,int x){
//std::cout<<bits<<" "<<x<<" send\n";
		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.first]){
						pq.push({relax_w+x.second,x.first});
					}
				}
				mode=CL;
			}
//std::cout<<relax_v<<" "<<relax_w<<"\n";
		}
	}
}
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]});
		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;
	Do();
}
void ReceiveB(bool x){
	buf[buf_size]=x;
	buf_size++;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 328 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 656 KB Output is correct
2 Runtime error 4 ms 456 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 328 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 328 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 328 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 328 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -