Submission #112730

#	Time	Username	Problem	Language	Result	Execution time	Memory
112730		Bruteforceman	Two Transportations (JOI19_transportations)	C++14	62 / 100	1844 ms	85552 KiB

Azer

#include "Azer.h"
#include "bits/stdc++.h"
using namespace std;
 
namespace {
	struct node {
		int x;
		int dist;
		node () {}
		node (int x, int dist) : x(x), dist(dist) {}
		bool operator < (node n) const {
			return dist > n.dist;
		}
	};
	const int inf = 1000000000;
	const int sz = 11 + 9;
	int N;
	vector <int> buf;
	priority_queue <node> Q; 
	int last;
	vector <pair <int, int>> G[2005];
	bool done[2005];
	int d[2005];
 
	void sendInfo(int x, int value) {
		for(int i = 0; i < 11; i++) {
			SendA((x >> i) & 1);
		}
		for(int i = 11; i < sz; i++) {
			SendA((value >> (i - 11)) & 1);
		}
	}
	node getInfo(vector <int> v) {
		node ans (0, 0);
		for(int i = 0; i < 11; i++) {
			if(v[i]) {
				ans.x |= 1 << i;
			}
		}
		for(int i = 11; i < sz; i++) {
			if(v[i]) {
				ans.dist |= 1 << (i - 11);
			}
		}
		return ans;
	}
}  // namespace
 
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) {
    G[U[i]].push_back(pair <int, int> (V[i], C[i]));
    G[V[i]].push_back(pair <int, int> (U[i], C[i]));
  }
  last = 0;
  for(auto i : G[0]) {
  	Q.push(node(i.first, i.second));
  }
  for(int i = 0; i < N; i++) {
  	d[i] = inf;
  }
  d[0] = 0;
  done[0] = true;
  node init = Q.empty() ? node(N, 0) : Q.top();
  sendInfo(init.x, init.dist);
}
 
void ReceiveA(bool x) {
	bool good = true; 
	for(int i = 0; i < N; i++) {
		if(!done[i]) {
			good = false;
			break;
		}
	}
	if(good) return ;
	buf.push_back(x);
	if(buf.size() == sz) {
		while(!Q.empty() && done[Q.top().x]) {
			Q.pop();
		}
		node A = Q.empty() ? node(N, inf) : Q.top();
		node B = getInfo(buf);
		B.dist += last;
		if(B.x == N) B.dist = inf;
		node opt;
		if(A.dist > B.dist) {
			opt = B;
		} else {
			opt = A;
		}
		done[opt.x] = true;
		last = d[opt.x] = opt.dist;
 
		for(auto i : G[opt.x]) {
			if(d[opt.x] + i.second < d[i.first]) {
				d[i.first] = d[opt.x] + i.second;
				Q.push(node(i.first, d[i.first]));
			}
		}
		while(!Q.empty() && done[Q.top().x]) {
			Q.pop();
		}
		if(!Q.empty()) {
			node sender = Q.top();
			sendInfo(sender.x, sender.dist - last);
		} else {
			sendInfo(N, 0);
		}
		buf.clear();
	}
}
 
std::vector<int> Answer() {
	vector <int> ans;
	for(int i = 0; i < N; i++) {
		ans.push_back(d[i]);
	}
	return ans;
}

Baijan

#include "Baijan.h"
#include "bits/stdc++.h"
using namespace std;
 
namespace {
	struct node {
		int x;
		int dist;
		node () {}
		node (int x, int dist) : x(x), dist(dist) {}
		bool operator < (node n) const {
			return dist > n.dist;
		}
	};
	const int inf = 1000000000;
	const int sz = 11 + 9;
	int N;
	vector <int> buf;
	priority_queue <node> Q; 
	int last;
	vector <pair <int, int>> G[2005];
	bool done[2005];
	int d[2005];
 
	void sendInfo(int x, int value) {
		for(int i = 0; i < 11; i++) {
			SendB((x >> i) & 1);
		}
		for(int i = 11; i < sz; i++) {
			SendB((value >> (i - 11)) & 1);
		}
	}
	node getInfo(vector <int> v) {
		node ans (0, 0);
		for(int i = 0; i < 11; i++) {
			if(v[i]) {
				ans.x |= 1 << i;
			}
		}
		for(int i = 11; i < sz; i++) {
			if(v[i]) {
				ans.dist |= 1 << (i - 11);
			}
		}
		return ans;
	}
}  // namespace
 
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  ::N = N;
  for (int i = 0; i < B; ++i) {
    G[S[i]].push_back(pair <int, int> (T[i], D[i]));
    G[T[i]].push_back(pair <int, int> (S[i], D[i]));
  }
  last = 0;
  for(auto i : G[0]) {
  	Q.push(node(i.first, i.second));
  }
  for(int i = 0; i < N; i++) {
  	d[i] = inf;
  }
  d[0] = 0;
  done[0] = true;
}
 
void ReceiveB(bool x) {
	bool good = true; 
	for(int i = 0; i < N; i++) {
		if(!done[i]) {
			good = false;
			break;
		}
	}
	if(good) return ;
	buf.push_back(x);
	if(buf.size() == sz) {
		while(!Q.empty() && done[Q.top().x]) {
			Q.pop();
		}
		node A = Q.empty() ? node(N, inf) : Q.top();
		node B = getInfo(buf);
 
		B.dist += last;
		if(B.x == N) B.dist = inf;
		node opt;
		if(A.dist >= B.dist) {
			opt = B;
		} else {
			opt = A;
		}
		sendInfo(opt.x, opt.dist - last);
		done[opt.x] = true;
		last = d[opt.x] = opt.dist;
 
		for(auto i : G[opt.x]) {
			if(d[opt.x] + i.second < d[i.first]) {
				d[i.first] = d[opt.x] + i.second;
				Q.push(node(i.first, d[i.first]));
			}
		}
		buf.clear();
	}
}

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