Submission #784268

#	Time	Username	Problem	Language	Result	Execution time	Memory
784268		AdamGS	Two Transportations (JOI19_transportations)	C++17	100 / 100	986 ms	57688 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
	const int LIM=2e3+7, INF=1e9+7;
	vector<pair<int,int>>V[LIM];
	int odl[LIM];
	int n, lst=0;
	int akt=0, li=0, stan=0;
	int moje, jego;
	priority_queue<pair<int,int>>q;
void wyslij(int x) {
	rep(i, 9) if(x&(1<<i)) SendA(1); else SendA(0);
}
void wyslij2(int x) {
	rep(i, 11) if(x&(1<<i)) SendA(1); else SendA(0);
}
void wysylam_odl() {
	while(!q.empty() && odl[q.top().nd]<INF) q.pop();
	if(!q.empty()) {
		moje=-q.top().st-lst;
		wyslij(moje);
	} else {
		moje=511;
		wyslij(moje);
	}
}
void wrzuc(int dys, int wierz) {
	dys+=lst;
	lst=dys;
	odl[wierz]=dys;
	for(auto i : V[wierz]) q.push({-odl[wierz]-i.nd, i.st});
}
}
void InitA(int _N, int _A, vector<int>A, vector<int>B, vector<int>C) {
	n=_N;
	rep(i, _A) {
		V[A[i]].pb({B[i], C[i]});
		V[B[i]].pb({A[i], C[i]});
	}
	rep(i, n) odl[i]=INF; 
	wrzuc(0, 0);
	wysylam_odl();
}
void ReceiveA(bool x) {
	if(x) li+=1<<akt;
	++akt;
	if(stan==0 && akt==9) {
		if(li==511) return;
		if(li<moje) {
			jego=li;
			akt=li=0;
			stan=1;
		} else {
			int dys=-q.top().st, wierz=q.top().nd; q.pop();
			wyslij2(wierz);
			wrzuc(dys-lst, wierz);
			akt=li=0;
			stan=2;
		}
	} else if(stan==1 && akt==11) {
		wrzuc(jego, li);
		akt=li=0;
		wysylam_odl();
		stan=0;
	} else if(stan==2 && akt==9) {
		jego=li;
		while(!q.empty() && odl[q.top().nd]<INF) q.pop();
		if(q.empty()) {
			wyslij(li);
			stan=1;
			akt=li=0;
			return;
		}
		int dys=-q.top().st, wierz=q.top().nd;
		if(dys-lst<li) {
			wyslij(dys-lst);
			wyslij2(wierz);
			q.pop();
			wrzuc(dys-lst, wierz);
			stan=2;
		} else {
			wyslij(li);
			stan=1;
		}
		akt=li=0;
	}
}
vector<int> Answer() {
  vector<int> ans(n);
  rep(i, n) ans[i]=odl[i];
  return ans;
}

Baijan

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
	const int LIM=2e3+7, INF=1e9+7;
	vector<pair<int,int>>V[LIM];
	int odl[LIM];
	int n, lst=0;
	int akt=0, li=0, stan=0;
	int moje, jego;
	priority_queue<pair<int,int>>q;
void wyslij(int x) {
	rep(i, 9) if(x&(1<<i)) SendB(1); else SendB(0);
}
void wyslij2(int x) {
	rep(i, 11) if(x&(1<<i)) SendB(1); else SendB(0);
}
void wysylam_odl() {
	while(!q.empty() && odl[q.top().nd]<INF) q.pop();
	if(!q.empty()) {
		moje=-q.top().st-lst;
		wyslij(moje);
	} else {
		moje=511;
		wyslij(moje);
	}
}
void wrzuc(int dys, int wierz) {
	dys+=lst;
	lst=dys;
	odl[wierz]=dys;
	for(auto i : V[wierz]) q.push({-odl[wierz]-i.nd, i.st});
}
}
void InitB(int _N, int _A, vector<int>A, vector<int>B, vector<int>C) {
	n=_N;
	rep(i, _A) {
		V[A[i]].pb({B[i], C[i]});
		V[B[i]].pb({A[i], C[i]});
	}
	rep(i, n) odl[i]=INF;
	wrzuc(0, 0);
	stan=2;
}
void ReceiveB(bool x) {
	if(x) li+=1<<akt;
	++akt;
	if(stan==0 && akt==9) {
		if(li==511) return;
		if(li<moje) {
			jego=li;
			akt=li=0;
			stan=1;
		} else {
			int dys=-q.top().st, wierz=q.top().nd; q.pop();
			wyslij2(wierz);
			wrzuc(dys-lst, wierz);
			akt=li=0;
			stan=2;
		}
	} else if(stan==1 && akt==11) {
		wrzuc(jego, li);
		akt=li=0;
		wysylam_odl();
		stan=0;
	} else if(stan==2 && akt==9) {
		jego=li;
		while(!q.empty() && odl[q.top().nd]<INF) q.pop();
		if(q.empty()) {
			wyslij(li);
			stan=1;
			akt=li=0;
			return;
		}
		int dys=-q.top().st, wierz=q.top().nd;
		if(dys-lst<li) {
			wyslij(dys-lst);
			wyslij2(wierz);
			q.pop();
			wrzuc(dys-lst, wierz);
			stan=2;
		} else {
			wyslij(li);
			stan=1;
		}
		akt=li=0;
	}
}

• 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