oj.uz

Submission #112658

# Submission time Handle Problem Language Result Execution time Memory
112658 2019-05-21T08:02:49 Z Bruteforceman Two Transportations (JOI19_transportations) C++14
0 / 100
 627 ms 1416 KB 
#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;

		// cout << "A have " << A.x << ' ' << A.dist << endl;
		// cout << "B send " << B.x << ' ' << B.dist << endl;

		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();
			// cout << "send " << sender.x << ' ' << sender.dist << endl;
			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;
}

#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);

		// cout << "B have " << A.x << ' ' << A.dist << endl;
		// cout << "A send " << B.x << ' ' << B.dist << endl;

		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.0

# Verdict Execution time Memory Grader output
1 Incorrect 627 ms 676 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1416 KB Output is correct
2 Incorrect 532 ms 880 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 488 ms 752 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 598 ms 644 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 598 ms 644 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 598 ms 644 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 627 ms 676 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -