Submission #409191

#	Time	Username	Problem	Language	Result	Execution time	Memory
409191		amoo_safar	Two Transportations (JOI19_transportations)	C++17	100 / 100	834 ms	48876 KiB

Azer

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

#define pb push_back
#define F first
#define S second

using namespace std;

typedef pair<int, int> pii;

namespace {

const int N = 2003;

int n;

int dis[N], mk[N], la = 0;
vector<pii> G[N];

int lst = 0, rq = 0;
int state = 0;
int msg = 0;
int dist = 0;

}  // namespace

void Send(int x, int bt){
	for(int i = 0; i < bt; i++){
		SendA(x & 1);
		x /= 2;
	}
}

void Find(){
	int mn = -1;

	for(int i = 0; i < n; i++){
		if(mk[i]) continue;
		if(mn == -1) mn = dis[i];
		mn = min(mn, dis[i]);
	}
	if(mn == -1) return ;
	mn -= la;
	mn = min(mn, 501);
	Send(mn, 9);

	lst = 0; rq = 9; state = 0; msg = 0;
}

void InitA(int _n, int A, vector<int> U, vector<int> V, vector<int> C) {
	fill(dis, dis + N, 500 * N);
	dis[0] = 0;

	n = _n;
	for (int i = 0; i < A; ++i) {
		G[U[i]].pb({V[i], C[i]});
		G[V[i]].pb({U[i], C[i]});
	}
	Find();
}

void Set(int idx, int dst){
	dis[idx] = dst;
	mk[idx] = 1;
	la = dst;
	for(auto [adj, w] : G[idx]){
		if(dis[adj] > dst + w)
			dis[adj] = dst + w;
	}
	Find();
}

void Response(){
	bool fl = false;
	int idx = -1;
	for(int i = 0; i < n; i++){
		if(mk[i] == 0 && dis[i] == la + msg) fl = true, idx = i;
	}
	if(!fl){
		dist = la + msg;
		state = 1;
		lst = 0; rq = 11;
		msg = 0;
		return ;
	}
	Send(idx, 11);
	Set(idx, la + msg);
}

void ReceiveA(bool x) {
	if(x)
		msg += (1 << lst);
	lst ++;
	if(lst < rq) return ;
	// cerr << "!A " << msg << ' ' << rq << '\n';
	if(state == 0)
		Response();
	else
		Set(msg, dist);
}

vector<int> Answer() {
	vector<int> ans(n);
	for(int i = 0; i < n; i++) {
		ans[i] = dis[i];
	}
	return ans;
}

Baijan

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

#define pb push_back
#define F first
#define S second

using namespace std;

typedef pair<int, int> pii;

namespace {

const int N = 2003;

int n;

int dis[N], mk[N], la = 0;
vector<pii> G[N];

int lst = 0, rq = 0;
int state = 0;
int msg = 0;
int dist = 0;

}  // namespace

void SendT(int x, int bt){
	for(int i = 0; i < bt; i++){
		SendB(x & 1);
		x /= 2;
	}
}

void SetT(int idx, int dst){
	dis[idx] = dst;
	la = dst;
	mk[idx] = 1;
	for(auto [adj, w] : G[idx]){
		if(dis[adj] > dst + w)
			dis[adj] = dst + w;
	}
	lst = 0; rq = 9; state = 0; msg = 0;
}
void Find(int def){
	int mn = -1;
	int idx = -1;
	for(int i = 0; i < n; i++){
		if(mk[i]) continue;
		if(mn == -1) mn = dis[i];
		mn = min(mn, dis[i]);
		if(mn == dis[i])
			idx = i;
	}
	if(mn == -1) return ;
	mn -= la;
	mn = min(mn, 501);

	SendT(min(mn, def), 9);
	if(def <= mn){
		lst = 0; rq = 11; state = 1; msg = 0;
		dist = def + la;
	} else {
		SendT(idx, 11);
		SetT(idx, mn + la);
	}
}

void InitB(int _n, int A, vector<int> U, vector<int> V, vector<int> C) {
	fill(dis, dis + N, 500 * N);
	n = _n;
	for (int i = 0; i < A; ++i) {
		G[U[i]].pb({V[i], C[i]});
		G[V[i]].pb({U[i], C[i]});
	}
	state = 0; rq = 9;
	lst = 0; msg = 0;
}

// void Response(){
// 	bool fl = false;
// 	int idx = -1;
// 	for(int i = 0; i < n; i++){
// 		if(mk[i] == 0 && dis[i] == la + msg) fl = true, idx = i;
// 	}
// 	if(!fl){
// 		dist = la + msg;
// 		state = 1;
// 		lst = 0; rq = 11;
// 		msg = 0;
// 		return ;
// 	}
// 	Send(idx, 11);
// 	Set(idx, la + msg);
// }

void ReceiveB(bool x) {
	if(x)
		msg += (1 << lst);
	lst ++;
	if(lst < rq) return ;
	// cerr << "!B " << msg << ' ' << rq << '\n';
	
	if(state == 0)
		Find(msg);
	else
		SetT(msg, dist);
}

• 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