Submission #565101

#	Time	Username	Problem	Language	Result	Execution time	Memory
565101		errorgorn	Two Transportations (JOI19_transportations)	C++17	100 / 100	842 ms	97208 KiB

Azer

#include "Azer.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {

int n,m;
vector<ii> al[2005];
int w[2005];
priority_queue<ii,vector<ii>,greater<ii> > pq;

queue<int> q;
void send(int i,int k){
	rep(bit,0,k){
		if (i&(1<<bit)) SendA(1);
		else SendA(0);
	}
}

int get(int k){
	int res=0;
	rep(bit,0,k){
		res|=q.front()<<bit;
		q.pop();
	}
	return res;
}

bool flag=false;
int PREV=0;
int u,W,W_other;

void add(int i,int j){
	//cout<<"debug A: "<<i<<" "<<j<<endl;
	
	PREV=w[i]=j;
	for (auto [it,w2]:al[i]){
		pq.push({j+w2,it});
	}
}

void proc(){
	u=-1,W=1e18;
	while (!pq.empty()){
		tie(W,u)=pq.top();
		if (w[u]!=-1){
			u=-1,W=1e18;
			pq.pop();
		}
		else break;
	}
	
	if (u==-1) send(511,9);
	else send(W-PREV,9);
}

} 

void InitA(signed N, signed A, std::vector<signed> U, std::vector<signed> V,
           std::vector<signed> C) {
			   
	n=N,m=A;
	rep(x,0,m){
		al[U[x]].pub({V[x],C[x]});
		al[V[x]].pub({U[x],C[x]});
	}
	
	memset(w,-1,sizeof(w));
	add(0,0);
}

void ReceiveA(bool x){
	q.push(x);
	
	if (!flag){
		if (sz(q)!=9) return;
		
		proc();
		
		W_other=get(9)+PREV;
		
		if (W<=W_other){ //A wins
			send(u,11);
			add(u,W);
		}
		else{
			flag=true;
		}
	}
	else{
		if (sz(q)!=11) return;
		
		u=get(11);
		add(u,W_other);
		
		flag=false;
	}
}

std::vector<signed> Answer() {
	vector<signed> res;
	rep(x,0,n) res.pub(w[x]);
	return res;
}

Baijan

#include "Baijan.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {

int n,m;
vector<ii> al[2005];
int w[2005];
priority_queue<ii,vector<ii>,greater<ii> > pq;

queue<int> q;
void send(int i,int k){
	rep(bit,0,k){
		if (i&(1<<bit)) SendB(1);
		else SendB(0);
	}
}

int get(int k){
	int res=0;
	rep(bit,0,k){
		res|=q.front()<<bit;
		q.pop();
	}
	return res;
}

bool flag=false;
int PREV=0;
int u,W,W_other;

void add(int i,int j){
	//cout<<"debug B: "<<i<<" "<<j<<endl;
	
	PREV=w[i]=j;
	for (auto [it,w2]:al[i]){
		pq.push({j+w2,it});
	}
}

int count=0;
void proc(){
	count++;
	if (count==n) return;
	
	u=-1,W=1e18;
	while (!pq.empty()){
		tie(W,u)=pq.top();
		if (w[u]!=-1){
			u=-1,W=1e18;
			pq.pop();
		}
		else break;
	}
	
	if (u==-1) send(511,9);
	else send(W-PREV,9);
}

};

void InitB(signed N, signed B, std::vector<signed> S, std::vector<signed> T,
           std::vector<signed> D) {

	n=N,m=B;
	rep(x,0,m){
		al[S[x]].pub({T[x],D[x]});
		al[T[x]].pub({S[x],D[x]});
	}
	
	memset(w,-1,sizeof(w));
	add(0,0);
	
	proc();
}

void ReceiveB(bool y){
	q.push(y);
	
	if (!flag){
		if (sz(q)!=9) return;
		
		W_other=get(9)+PREV;
		
		if (W<W_other){ //B wins
			add(u,W);
			send(u,11);
			proc();
		}
		else{
			flag=true;
		}
	}
	else{
		if (sz(q)!=11) return;
		
		u=get(11);
		add(u,W_other);
		
		flag=false;
		proc();
	}
}

• 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