Submission #1150285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150285		fatman87878	Two Transportations (JOI19_transportations)	C++20	100 / 100	314 ms	49064 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;

	bitset<maxN> vis;
	
	// 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(;!pq.empty();){
			auto [d,u] = pq.top();
			if(vis[u]){
				pq.pop();
				continue;
			}
			nowdis = d;
			sendDis(d-lstdis);
			val = 0;
			type = 1;
			len = 0;
			return;
		}
		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+1,dis+n,1e9);
	determined++;
	vis[0] = 1;
	for(auto [v,c]:adj[0])if(dis[v]>dis[0]+c)
		pq.emplace(dis[v]=dis[0]+c,v);
	push1();
}

void ReceiveA(bool x) {
	len++;
	val<<=1;
	val|=x;
	int flag = 0,u;
	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(u = pq.top().second);
			pq.pop();
			flag = 1;
		}
	}
	else {
		if(len==11){
			//cout<<"A receives index "<<val<<"\n";
			dis[u = val] = lstdis;
			flag = 1;
		}
	}
	if(!flag)return;
	determined++;
	vis[u] = 1;
	for(auto [v,c]:adj[u])if(dis[v]>dis[u]+c)
		pq.emplace(dis[v]=dis[u]+c,v);
	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;

	bitset<maxN> vis;

	// 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(;!pq.empty();){
			auto [d,u] = pq.top();
			if(vis[u]){
				pq.pop();
				continue;
			}
			nowdis = d;
			sendDis(d-lstdis);
			val = 0;
			type = 1;
			len = 0;
			return;
		}
		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+1,dis+n,1e9);
	determined++;
	vis[0] = 1;
	for(auto [v,c]:adj[0])if(dis[v]>dis[0]+c)
		pq.emplace(dis[v]=dis[0]+c,v);
	push1();
}

void ReceiveB(bool x) {
	len++;
	val<<=1;
	val|=x;
	int flag = 0,u = 0;
	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(u = pq.top().second);
			pq.pop();
			flag = 1;
		}
	}
	else {
		if(len==11){
			//cout<<"B receives index "<<val<<"\n";
			dis[u = val] = lstdis;
			flag = 1;
		}
	}
	if(!flag)return;
	determined++;
	vis[u] = 1;
	for(auto [v,c]:adj[u])if(dis[v]>dis[u]+c)
		pq.emplace(dis[v]=dis[u]+c,v);
	push1();
}

• 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: 16 / 16