Submission #132363

#	Time	Username	Problem	Language	Result	Execution time	Memory
132363		sebinkim	Two Transportations (JOI19_transportations)	C++14	38 / 100	1463 ms	61144 KiB

Azer

#include <bits/stdc++.h>

#include "Azer.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 20;

namespace{
	priority_queue <pii> Q;
	vector <pii> G[2020];
	vector <int> D;
	bool chk[2020];
	int _st, _val, _cnt;
	int n;
}

static void sendint(int x, int l) { for(; l--; ) SendA((x & (1 << l))? 1 : 0); }

static void apply(int p, int d)
{
//	printf("applyA %d %d\n", p, d);
	chk[p] = 1; D[p] = d;
	
	for(pii &t: G[p]){
		if(!chk[t.first] && D[t.first] > d + t.second){
			D[t.first] = d + t.second;
			Q.emplace(-d - t.second, t.first);
		}
	}
}

static void check()
{
	int p, d;
	
	for(; !Q.empty(); Q.pop()){
		tie(d, p) = Q.top(); d = -d;
		if(!chk[p] && d == D[p]) break;
	}
	
	if(Q.empty()) return;
	
	_st = 0;
	
	tie(d, p) = Q.top(); d = -d;
	
	sendint(p, ID);
	sendint(d, DIST);
}

void InitA(int N, int A, vector <int> U, vector <int> V, vector<int> C)
{
	n = N; D.resize(n, 0);
	
	int i;
	
	for(i=0; i<A; i++){
		G[U[i]].emplace_back(V[i], C[i]);
		G[V[i]].emplace_back(U[i], C[i]);
	}
	
	for(i=1; i<n; i++){
		D[i] = (1 << DIST) - 1;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
	check();
}

void ReceiveA(bool x)
{
//	printf("ReceiveA %d\n", x);
	if(!_st){
		if(!x){
			int d, p;
			tie(d, p) = Q.top();
			d = -d; Q.pop();
			apply(p, d); check();
		}
		else _st = 1;
	}
	else{
		_val = _val << 1 | x; _cnt ++;
	
		if(_cnt == ID + DIST){
			int p = _val >> DIST;
			int d = _val & ((1 << DIST) - 1);
			_val = 0; _cnt = 0; _st = 0;
			apply(p, d); check();
		}
	}
}

vector <int> Answer() { return D; }

Baijan

#include <bits/stdc++.h>

#include "Baijan.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 20;

namespace{
	priority_queue <pii> Q;
	vector <pii> G[2020];
	vector <int> D;
	bool chk[2020];
	int _st, _val, _cnt;
	int n;
}

static void sendint(int x, int l) { for(; l--; ) SendB((x & (1 << l))? 1 : 0); }

static void apply(int p, int d)
{
//	printf("applyB %d %d\n", p, d);
	chk[p] = 1; D[p] = d;
	
	for(pii &t: G[p]){
		if(!chk[t.first] && D[t.first] > d + t.second){
			D[t.first] = d + t.second;
//			printf("updateB %d %d\n", t.first, d + t.second);
			Q.emplace(-d - t.second, t.first);
		}
	}
}

static void check(int pa, int da)
{
	int p, d, pb, db;
	
	for(; !Q.empty(); Q.pop()){
		tie(db, pb) = Q.top(); db = -db;
		if(!chk[pb] && D[pb] == db) break;
	}
	
	tie(db, pb) = Q.top(); db = -db;
	
	if(da < db){
		p = pa, d = da;
		SendB(0);
	}
	else{
		p = pb, d = db; Q.pop();
		SendB(1);
		sendint(p, ID);
		sendint(d, DIST);
	}
	
	apply(p, d);
}

void InitB(int N, int B, vector <int> S, vector<int> T, vector<int> C)
{
	n = N; D.resize(n, 0);
	
	int i;
	
	for(i=0; i<B; i++){
		G[S[i]].emplace_back(T[i], C[i]);
		G[T[i]].emplace_back(S[i], C[i]);
	}
	
	for(i=1; i<n; i++){
		D[i] = (1 << DIST) - 1;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
}

void ReceiveB(bool y)
{
//	printf("ReceiveB %d\n", y);
	_val = _val << 1 | y; _cnt ++;
	
	if(_cnt == ID + DIST){
		int p = _val >> DIST;
		int d = _val & ((1 << DIST) - 1);
		_val = 0; _cnt = 0;
		check(p, d);
	}
}

Compilation message (stderr)

Baijan.cpp:17:6: warning: '{anonymous}::_st' defined but not used [-Wunused-variable]
  int _st, _val, _cnt;
      ^~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 38 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16