Submission #532170

#	Time	Username	Problem	Language	Result	Execution time	Memory
532170		8e7	Two Transportations (JOI19_transportations)	C++17	100 / 100	782 ms	48876 KiB

Azer

#include "Azer.h"
#include <vector>
#include <iostream>
#include "assert.h"
using namespace std;
#define ll long long
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second

namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif

const int inf = (1LL<<28) - 1;
const int wbit = 9, nbit = 11;
int N;
int done = 0;
int dis[maxn];
bool vis[maxn];
vector<pii> adj[maxn];

vector<bool> buf;
int wait = 0; //0:weight, 1:node

int cur = 0, bind = 0, bval = 0;

int uind = 0, uval = 0;


void send_weight(int w) {
	assert(w >= 0);
	if (w >= (1<<wbit)) w = (1<<wbit) - 1;
	for (int i = 0;i < wbit;i++) {
		SendA(w & (1<<i));
	}
}
void send_node(int id) {
	assert(id >= 0);
	for (int i = 0;i < nbit;i++) {
		SendA(id & (1<<i));
	}
}
int getnum() {
	int siz = 1;
	if (wait == 0) siz = wbit;
	else if (wait == 1) siz = nbit;
	int ret = 0;
	for (int i = 0;i < siz;i++) {
		ret = ret+ (buf[i] ? 1<<i : 0);
	}
	buf.erase(buf.begin(), buf.begin() + siz);
	return ret;
}
void get_best() {
	debug("A dis");
	//pary(dis, dis + N);
	//pary(vis, vis + N);
	int best = inf;
	bind = 0;
	for (int j = 0;j < N;j++) {
		if (!vis[j] && dis[j] < best) {
			best = dis[j];
			bind = j;
		}
	}
	wait = 0;
	debug("Send weight A ", cur, best - cur);
	bval = best - cur;
	send_weight(best - cur);
}

void solve() {
	if (wait == 0 && buf.size() >= wbit) {
		uval = getnum();
		if (bval <= uval) {
			for (auto [v, e]:adj[bind]) {
				if (dis[bind] + e < dis[v]) {
					dis[v] = dis[bind] + e;
				}
			}
			vis[bind] = 1;
			cur = dis[bind];
			if (++done >= N) Answer();
			else {
				debug("Send A node ", bind);
				send_node(bind);
				get_best();
			}	
			return;
		}
		wait = 1;
		solve();
	} else if (wait == 1 && buf.size() >= nbit){
		uind = getnum();
		dis[uind] = uval + cur;
		vis[uind] = 1;
		for (auto [v, e]:adj[uind]) {
			if (dis[uind] + e < dis[v]) {
				dis[v] = dis[uind] + e;
			}
		}
		cur += uval;
		if (++done >= N) Answer();
		else {
			get_best();
		}
	}
}

}  // namespace
std::vector<int> Answer() {
	std::vector<int> ans(N);
	for (int k = 0; k < N; ++k) {
		ans[k] = dis[k];
	}
	return ans;
}



void ReceiveA(bool x) {
	buf.push_back(x); 
	solve();	
}

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]].push_back({V[i], C[i]});
		adj[V[i]].push_back({U[i], C[i]});
	}
	for (int i = 0;i < N;i++) dis[i] = inf, vis[i] = 0;
	dis[0] = 0;
	get_best();	
}

Baijan

#include "Baijan.h"
#include <vector>
#include <iostream>
#include "assert.h"
using namespace std;

#define ll long long
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second

namespace {
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
const int inf = (1LL<<28) - 1;
const int wbit = 9, nbit = 11;
int N;
int done = 0;
int dis[maxn];
bool vis[maxn];
vector<pii> adj[maxn];

vector<bool> buf;
int wait = 0; //0:weight, 1:node

int cur = 0, bind = 0;

int uind = 0, uval = 0;


void send_weight(int w) {
	assert(w >= 0);
	if (w >= (1<<wbit)) w = (1<<wbit) - 1;
	for (int i = 0;i < wbit;i++) {
		SendB(w & (1<<i));
	}
}
void send_node(int id) {
	assert(id >= 0);
	for (int i = 0;i < nbit;i++) {
		SendB(id & (1<<i));
	}
}

int getnum() {
	int siz = 1;
	if (wait == 0) siz = wbit;
	else if (wait == 1) siz = nbit;
	int ret = 0;
	for (int i = 0;i < siz;i++) {
		ret = ret + (buf[i] ? 1<<i : 0);
	}
	buf.erase(buf.begin(), buf.begin() + siz);
	return ret;
}
void get_best() {
	int best = inf;
	bind = 0;
	for (int j = 0;j < N;j++) {
		if (!vis[j] && dis[j] < best) {
			best = dis[j];
			bind = j;
		}
	}
	debug("B best", bind, cur, best - cur, uval);
	send_weight(best - cur);
	if (best - cur < uval) {
		debug("Send b wei ", cur, best - cur);
		send_node(bind);
		for (auto [v, e]:adj[bind]) {
			if (dis[bind] + e < dis[v]) {
				dis[v] = dis[bind] + e;
			}
		}
		debug("vis b", bind);
		vis[bind] = 1;
		cur = dis[bind];
		wait = 0;
	} else {
		wait = 1;
	}
}

void solve() {
	if (wait == 0 && buf.size() >= wbit) {
		uval = getnum();
		get_best();
	} else if (wait == 1 && buf.size() >= nbit){
		uind = getnum();
		debug("read B node", uind);
		dis[uind] = uval + cur;
		vis[uind] = 1;
		for (auto [v, e]:adj[uind]) {
			if (dis[uind] + e < dis[v]) {
				dis[v] = dis[uind] + e;
			}
		}
		cur += uval;
		wait = 0;
	}
}
}  // namespace
void ReceiveB(bool x) {
	buf.push_back(x); 
	solve();	
}

void InitB(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]].push_back({V[i], C[i]});
		adj[V[i]].push_back({U[i], C[i]});
	}
	for (int i = 0;i < N;i++) dis[i] = inf, vis[i] = 0;
	dis[0] = 0;
}

Compilation message (stderr)

Azer.cpp: In function 'void {anonymous}::get_best()':
Azer.cpp:21:20: warning: statement has no effect [-Wunused-value]
   21 | #define debug(...) 0
      |                    ^
Azer.cpp:66:2: note: in expansion of macro 'debug'
   66 |  debug("A dis");
      |  ^~~~~
Azer.cpp:21:20: warning: statement has no effect [-Wunused-value]
   21 | #define debug(...) 0
      |                    ^
Azer.cpp:78:2: note: in expansion of macro 'debug'
   78 |  debug("Send weight A ", cur, best - cur);
      |  ^~~~~
Azer.cpp: In function 'void {anonymous}::solve()':
Azer.cpp:21:20: warning: statement has no effect [-Wunused-value]
   21 | #define debug(...) 0
      |                    ^
Azer.cpp:96:5: note: in expansion of macro 'debug'
   96 |     debug("Send A node ", bind);
      |     ^~~~~

Baijan.cpp: In function 'void {anonymous}::get_best()':
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 0
      |                    ^
Baijan.cpp:75:2: note: in expansion of macro 'debug'
   75 |  debug("B best", bind, cur, best - cur, uval);
      |  ^~~~~
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 0
      |                    ^
Baijan.cpp:78:3: note: in expansion of macro 'debug'
   78 |   debug("Send b wei ", cur, best - cur);
      |   ^~~~~
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 0
      |                    ^
Baijan.cpp:85:3: note: in expansion of macro 'debug'
   85 |   debug("vis b", bind);
      |   ^~~~~
Baijan.cpp: In function 'void {anonymous}::solve()':
Baijan.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 0
      |                    ^
Baijan.cpp:100:3: note: in expansion of macro 'debug'
  100 |   debug("read B node", uind);
      |   ^~~~~
Baijan.cpp: At global scope:
Baijan.cpp:28:5: warning: '{anonymous}::done' defined but not used [-Wunused-variable]
   28 | int done = 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