oj.uz

Submission #112728

# Submission time Handle Problem Language Result Execution time Memory
112728 2019-05-21T16:14:46 Z Bruteforceman Two Transportations (JOI19_transportations) C++14
0 / 100
 3000 ms 23552 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) {
		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;
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 660 ms 752 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 1248 KB Output is correct
2 Incorrect 654 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 554 ms 880 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 1280 KB Output is correct
2 Correct 708 ms 1264 KB Output is correct
3 Correct 2501 ms 23552 KB Output is correct
4 Correct 597 ms 1592 KB Output is correct
5 Correct 2196 ms 17264 KB Output is correct
6 Correct 628 ms 1448 KB Output is correct
7 Correct 642 ms 1504 KB Output is correct
8 Correct 660 ms 1536 KB Output is correct
9 Execution timed out 3000 ms 18008 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 1280 KB Output is correct
2 Correct 708 ms 1264 KB Output is correct
3 Correct 2501 ms 23552 KB Output is correct
4 Correct 597 ms 1592 KB Output is correct
5 Correct 2196 ms 17264 KB Output is correct
6 Correct 628 ms 1448 KB Output is correct
7 Correct 642 ms 1504 KB Output is correct
8 Correct 660 ms 1536 KB Output is correct
9 Execution timed out 3000 ms 18008 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 1280 KB Output is correct
2 Correct 708 ms 1264 KB Output is correct
3 Correct 2501 ms 23552 KB Output is correct
4 Correct 597 ms 1592 KB Output is correct
5 Correct 2196 ms 17264 KB Output is correct
6 Correct 628 ms 1448 KB Output is correct
7 Correct 642 ms 1504 KB Output is correct
8 Correct 660 ms 1536 KB Output is correct
9 Execution timed out 3000 ms 18008 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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