제출 #112728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112728		Bruteforceman	Two Transportations (JOI19_transportations)	C++14	0 / 100	3000 ms	23552 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) {
		if(x == N) value = 0;
		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;
	}
	node getOpt() {
		node opt (N, inf);
		for(int i = 0; i < N; i++) {
			if(!done[i]) {
				for(auto j : G[i]) {
					if(done[j.first] && d[j.first] + j.second < opt.dist) {
						opt = node(i, d[j.first] + j.second);
					}
				}
			}
		}
		return opt;
	}
}  // 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(int i = 0; i < N; i++) {
  	d[i] = inf;
  }
  d[0] = 0;
  done[0] = true;
  node init = getOpt();
  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) {
		node A = getOpt();
		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;

		node sender = getOpt();
		sendInfo(sender.x, sender.dist - last);
		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) {
		if(x == N) value = 0;
		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;
	}
	node getOpt() {
		node opt (N, inf);
		for(int i = 0; i < N; i++) {
			if(!done[i]) {
				for(auto j : G[i]) {
					if(done[j.first] && d[j.first] + j.second < opt.dist) {
						opt = node(i, d[j.first] + j.second);
					}
				}
			}
		}
		return opt;
	}
}  // 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(int i = 0; i < N; i++) {
  	d[i] = inf;
  }
  d[0] = 0;
  done[0] = true;

  // node init = Q.empty() ? node(N, 0) : Q.top();
  // cout << init.x << " " << init.dist << endl;
}

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) {
		node A = getOpt();
		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;
		buf.clear();
	}
}

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