Submission #239923

#	Time	Username	Problem	Language	Result	Execution time	Memory
239923		b00n0rp	Two Transportations (JOI19_transportations)	C++17	100 / 100	2250 ms	86512 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))

namespace {

	int N;
	vpii adj[2005];
	int dist[2005],done[2005];
	int count = 1;
	int global = 0;
	int pend;
	int pendtype; // 0 = dist,1 = node
	int verA,distA,verB,distB;
	PQD(pii) pq;

	void send(int x, int len){
		if(x >= (1<<len)) x = (1<<len)-1;
		FORD(i,len-1,0) SendA((x>>i)&1);
	}	

	void refresh(){
		while(pq.size()){
			int u = pq.top().S;
			pq.pop();
			for(auto v:adj[u]){
				if(dist[v.F] > dist[u]+v.S){
					dist[v.F] = dist[u]+v.S;
					pq.push({dist[v.F],v.F});
				}
			}
		}
		verB = 0;
		distB = 0;
	}

	void do_next(){
		if(count == N) return;
		count++;
		refresh();
		int u = -1;
		REP(i,N){
			if(done[i]) continue;
			if(u == -1 or dist[i] < dist[u]) u = i;
		}
		pend = 9;
		pendtype = 0;
		verA = u;
		distA = dist[u];
		// cerr << "Azer send dist: " << distA << endl;
		send(min(distA-global,(1<<9)-1),9);

	}

}  // namespace

void InitA(int N, int A, vi U, vi V, vi C) {
	::N = N;
	REP(i,A){
		adj[U[i]].pb({V[i],C[i]});
		adj[V[i]].pb({U[i],C[i]});
	}
	REP(i,N) dist[i] = (1<<20)-1;
	dist[0] = 0;
	done[0] = 1;
	pq.push({0,0});

	do_next();

}

void ReceiveA(bool x){
	pend--;
	if(pendtype == 1){
		verB += ((int) x)*(1<<(pend));
		if(pend == 0){
			dist[verB] = distB; 
			done[verB] = 1;
			pq.push({distB,verB});
			refresh();
			do_next();
		}	
	}
	else{
		distB += ((int) x)*(1<<(pend));
		if(pend == 0){
			distB += global;
			if(distA < distB){
				global = distA;
				done[verA] = 1;
				// cerr << "Azer send ver: " << verA << endl;
				send(verA,11);
				do_next();
			}
			else{
				global = distB;
				pend = 11;
				pendtype = 1;
			}
		}
	}
}

vi Answer() {
  vi vd;
  REP(i,N) vd.pb(dist[i]);
  return vd;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define ITR :: iterator it
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define TR(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define sqr(x) ((x)*(x))
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))


namespace {

	int N;
	vpii adj[2005];
	int dist[2005],done[2005];
	int pend = 9;
	int pendtype = 0; // 0 = dist,1 = node
	int global = 0;
	int verA,distA,verB,distB;
	PQD(pii) pq;

	void send(int x, int len){
		if(x >= (1<<len)) x = (1<<len)-1;
		FORD(i,len-1,0) SendB((x>>i)&1);
	}	

	void refresh(){
		while(pq.size()){
			int u = pq.top().S;
			pq.pop();
			for(auto v:adj[u]){
				if(dist[v.F] > dist[u]+v.S){
					dist[v.F] = dist[u]+v.S;
					pq.push({dist[v.F],v.F});
				}
			}
		}
		verA = 0;
		distA = 0;
	}

	void do_next(){
		int u = -1;
		REP(i,N){
			if(done[i]) continue;
			if(u == -1 or dist[i] < dist[u]) u = i;
		}
		verB = u;
		distB = dist[u];
		int diff = distB-global;
		if(distA < distB){
			global = distA;
			pend = 11;
			pendtype = 1;
			// cerr << "Baijan send dist: " << distB << endl;
			send(min(diff,(1<<9)-1),9);
		}
		else{
			dist[verB] = distB;
			done[verB] = 1;
			global = distB;
			refresh();
			pend = 9;
			pendtype = 0;
			// cerr << "Baijan send dist: " << distB << endl;
			// cerr << "Baijan send ver: " << verB << endl;
			send(min(diff,(1<<9)-1),9);
			send(verB,11);
		}
	}

}  // namespace

void InitB(int N, int B, vi S, vi T, vi D) {
	::N = N;
	REP(i,B){
		adj[S[i]].pb({T[i],D[i]});
		adj[T[i]].pb({S[i],D[i]});
	}
	REP(i,N) dist[i] = (1<<20)-1;
	dist[0] = 0;
	done[0] = 1;
	pq.push({0,0});
	refresh();
}

void ReceiveB(bool y) {
	pend--;
	if(pendtype == 1){
		verA += ((int) y)*(1<<(pend));
		if(pend == 0){
			dist[verA] = distA; 
			done[verA] = 1;
			pq.push({distA,verA});
			refresh();
			pend = 9;
			pendtype = 11;
		}
	}
	else{
		distA += ((int) y)*(1<<(pend));
		if(pend == 0){
			distA += global;
			do_next();
		}
	}
	
}

• 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