제출 #1150236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150236		fatman87878	Two Transportations (JOI19_transportations)	C++20	6 / 100	177 ms	10368 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

namespace {

	constexpr int maxN=2e3+5;

	int n,dis[maxN],lstdis,nowdis,len,type,val,determined;
	
	// type 1 : dis
	// type 2 : idx
	
	vector<pair<int,int>> adj[maxN];
	
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	
	inline void sendIdx(int v){
		//cout<<"A send idx "<<v<<'\n';
		for(int i = 11;i--;)SendA(v>>i&1);
	}
	
	inline void sendDis(int v){
		//cout<<"A send dist "<<v<<'\n';
		for(int i = 9;i--;)SendA(v>>i&1);
	}
	
	inline void push1(){
		for(int cnt = 1;!pq.empty();){
			auto [d,u] = pq.top();
			if(d!=dis[u]){
				pq.pop();
				continue;
			}
			if(!cnt){
				nowdis = d;
				sendDis(d-lstdis);
				val = 0;
				type = 1;
				len = 0;
				return;
			}
			pq.pop();
			cnt--;
			determined++;
			for(auto [v,c]:adj[u])if(dis[v]>dis[u]+c)pq.emplace(dis[v]=dis[u]+c,v);
		}
		if(determined==n)return;
		nowdis = 511+lstdis;
		sendDis(511);
		val = 0;
		type = 1;
		len = 0;
	}
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
	n=N;
	for(int i = 0;i<A;i++){
		adj[U[i]].emplace_back(V[i],C[i]);
		adj[V[i]].emplace_back(U[i],C[i]);
	}
	fill(dis,dis+n,1e9);
	pq.emplace(dis[0] = 0,0);
	push1();
}

void ReceiveA(bool x) {
	len++;
	val<<=1;
	val|=x;
	if(type==1){
		if(len==9){
			//cout<<"A receives dist "<<val<<'\n';
			if(nowdis>=val+lstdis){
				lstdis += val;
				val = 0;
				type = 2;
				len = 0;
				return;
			}
			lstdis = nowdis;
			sendIdx(pq.top().second);
			push1();
		}
	}
	else {
		if(len==11){
			//cout<<"A receives index "<<val<<"\n";
			pq.emplace(dis[val] = lstdis,val);
			push1();
		}
	}
}

std::vector<int> Answer() {
	vector<int> res(n);
	for(int i = 0;i<n;i++)res[i] = dis[i];
	return res;
}

Baijan

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

namespace {

	constexpr int maxN=2e3+5;

	int n,dis[maxN],lstdis,nowdis,len,type,val,determined;

	// type 1 : dis
	// type 2 : idx
	
	vector<pair<int,int>> adj[maxN];
	
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	
	inline void sendIdx(int v){
		//cout<<"B send idx "<<v<<'\n';
		for(int i = 11;i--;)SendB(v>>i&1);
	}
	
	inline void sendDis(int v){
		//cout<<"B send dist "<<v<<'\n';
		for(int i = 9;i--;)SendB(v>>i&1);
	}
	
	inline void push1(){
		for(int cnt = 1;!pq.empty();){
			auto [d,u] = pq.top();
			if(d!=dis[u]){
				pq.pop();
				continue;
			}
			if(!cnt){
				nowdis = d;
				sendDis(d-lstdis);
				val = 0;
				type = 1;
				len = 0;
				return;
			}
			pq.pop();
			cnt--;
			determined++;
			for(auto [v,c]:adj[u])if(dis[v]>dis[u]+c)pq.emplace(dis[v]=dis[u]+c,v);
		}
		if(determined==n)return;
		nowdis = 511+lstdis;
		sendDis(511);
		val = 0;
		type = 1;
		len = 0;
	}
}

void InitB(int N, int B, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
	n=N;
	for(int i = 0;i<B;i++){
		adj[U[i]].emplace_back(V[i],C[i]);
		adj[V[i]].emplace_back(U[i],C[i]);
	}
	fill(dis,dis+n,1e9);
	pq.emplace(dis[0] = 0,0);
	push1();
}

void ReceiveB(bool x) {
	len++;
	val<<=1;
	val|=x;
	if(type==1){
		if(len==9){
			//cout<<"B receives dist "<<val<<'\n';
			if(nowdis>val+lstdis){
				lstdis += val;
				val = 0;
				type = 2;
				len = 0;
				return;
			}
			lstdis = nowdis;
			sendIdx(pq.top().second);
			push1();
		}
	}
	else {
		if(len==11){
			//cout<<"B receives index "<<val<<"\n";
			pq.emplace(dis[val] = lstdis,val);
			push1();
		}
	}
}

• Subtask 1: 6 / 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