oj.uz

Submission #122936

# Submission time Handle Problem Language Result Execution time Memory
122936 2019-06-29T15:10:32 Z atoiz Two Transportations (JOI19_transportations) C++14
6 / 100
 1264 ms 19880 KB 
#include "Azer.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 2010, INF = 1e8;

namespace {
	struct Edge
	{
		int w, v;
		Edge(int _w, int _v): w(_w), v(_v) {}
		bool operator< (const Edge &e) const { return w > e.w; }
	};
	int N;
	vector<Edge> G[MAXN];
	priority_queue<Edge> pq;
	vector<int> dist;
	vector<bool> received, done;
	int prvU, lastW, cnt;

	const int DIST_BITS = 9, VERTEX_BITS = 11;
	const int DIST = 0, VERTEX = 1;
	int state; 

	int findNxtU()
	{
		while (!pq.empty()) {
			auto a = pq.top();
			if (done[a.v] || dist[a.v] != a.w) { pq.pop(); continue; }
			return a.v;
		}
		return -1;
	}

	void update(int u)
	{
		assert(done[u] == 0);
		++cnt;
		done[u] = 1;
		for (auto &a : G[u]) {
			if (dist[a.v] > dist[u] + a.w) pq.emplace(dist[a.v] = dist[u] + a.w, a.v);
		}
	}
}

void InitA(int _N, int A, vector<int> U, vector<int> V, vector<int> C)
{
	N = _N;
	for (int i = 0; i < A; ++i) {
		G[U[i]].emplace_back(C[i], V[i]);
		G[V[i]].emplace_back(C[i], U[i]);
	}
	dist.assign(N, INF);
	done.assign(N, 0);

	dist[prvU = 0] = 0;	
	update(0);
	state = DIST;
}

void ReceiveA(bool b)
{
	received.push_back(b);
	if (state == DIST) {
		if (received.size() != DIST_BITS) return;

		int wB = dist[prvU];
		for (int i = 0; i < DIST_BITS; ++i) if (received[i]) wB += (1 << i);
		received.clear();

		int nxtU = findNxtU();
		int wA = (nxtU >= 0 ? dist[nxtU] - dist[prvU] : (1 << DIST_BITS) - 1);
		// cerr << "A: " << nxtU << " - " << wA << ", " << prvU << " - " << dist[prvU] << endl;
		for (int i = 0; i < DIST_BITS; ++i) SendA((wA >> i) & 1);
		wA += dist[prvU];

		if (wA < wB) {
			for (int i = 0; i < VERTEX_BITS; ++i) SendA((nxtU >> i) & 1);
			update(nxtU);

			prvU = nxtU;
			state = DIST;
		} else {
			lastW = wB;
			state = VERTEX;
		}
	} else if (state == VERTEX) {
		if (received.size() != VERTEX_BITS) return;

		int u = 0;
		for (int i = 0; i < VERTEX_BITS; ++i) if (received[i]) u += (1 << i);
		received.clear();

		// if (u == 3) cout << "SSSS " << prvU << ' ' << dist[prvU] << ' ' << lastW << endl;
		dist[u] = lastW;
		update(u);

		prvU = u;
		state = DIST;
	}
}

vector<int> Answer() { return dist; }
#include "Baijan.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 2010, INF = 1e8;

namespace {
	struct Edge
	{
		int w, v;
		Edge(int _w, int _v): w(_w), v(_v) {}
		bool operator< (const Edge &e) const { return w > e.w; }
	};
	int N;
	vector<Edge> G[MAXN];
	priority_queue<Edge> pq;
	vector<int> dist;
	vector<bool> received, done;
	int prvU, lastW, cnt;

	const int DIST_BITS = 9, VERTEX_BITS = 11;
	const int DIST = 0, VERTEX = 1;
	int state; 

	int findNxtU()
	{
		while (!pq.empty()) {
			auto a = pq.top();
			if (done[a.v] || dist[a.v] != a.w) { pq.pop(); continue; }
			return a.v;
		}
		return -1;
	}

	void update(int u)
	{
		assert(done[u] == 0);
		++cnt;
		done[u] = 1;
		for (auto &a : G[u]) {
			if (dist[a.v] > dist[u] + a.w) pq.emplace(dist[a.v] = dist[u] + a.w, a.v);
		}
	}

	void newChat()
	{
		if (cnt == N) return;
		int nxtU = findNxtU();
		int w = (nxtU >= 0 ? dist[nxtU] - dist[prvU] : (1 << DIST_BITS) - 1);
		state = DIST;
		// cerr << "B: " << nxtU << " - " << w << ", " << prvU << " - " << dist[prvU] << endl;
		for (int i = 0; i < DIST_BITS; ++i) SendB((w >> i) & 1);
	}
}

void InitB(int _N, int A, vector<int> U, vector<int> V, vector<int> C)
{
	N = _N;
	for (int i = 0; i < A; ++i) {
		G[U[i]].emplace_back(C[i], V[i]);
		G[V[i]].emplace_back(C[i], U[i]);
	}
	dist.assign(N, INF);
	done.assign(N, 0);

	cnt = 0;
	dist[prvU = 0] = 0;	
	update(0);

	newChat();
}

void ReceiveB(bool b)
{
	received.push_back(b);
	if (state == DIST) {
		if (received.size() != DIST_BITS) return;

		int wA = dist[prvU];
		for (int i = 0; i < DIST_BITS; ++i) if (received[i]) wA += (1 << i);
		received.clear();

		int nxtU = findNxtU();
		int wB = (nxtU >= 0 ? dist[nxtU] - dist[prvU] : (1 << DIST_BITS) - 1);

		if (wA < wB) {
			lastW = wA;
			state = VERTEX;
		} else {
			assert(nxtU >= 0);
			for (int i = 0; i < VERTEX_BITS; ++i) SendB((nxtU >> i) & 1);
			update(nxtU);

			prvU = nxtU;
			newChat();
		}
	} else if (state == VERTEX) {
		if (received.size() != VERTEX_BITS) return;

		int u = 0;
		for (int i = 0; i < VERTEX_BITS; ++i) if (received[i]) u += (1 << i);
		received.clear();

		dist[u] = lastW;
		update(u);

		prvU = u;
		newChat();
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 1448 KB Output is correct
2 Correct 4 ms 1208 KB Output is correct
3 Correct 1008 ms 1600 KB Output is correct
4 Correct 1264 ms 19880 KB Output is correct
5 Correct 66 ms 1760 KB Output is correct
6 Correct 976 ms 4320 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 944 KB Output is correct
2 Failed 6 ms 1160 KB Expected integer, but "prog2:" found (Baijan)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Failed 14 ms 964 KB Expected integer, but "prog2:" found (Baijan)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 1448 KB Output is correct
2 Correct 4 ms 1208 KB Output is correct
3 Correct 1008 ms 1600 KB Output is correct
4 Correct 1264 ms 19880 KB Output is correct
5 Correct 66 ms 1760 KB Output is correct
6 Correct 976 ms 4320 KB Output is correct
7 Correct 4 ms 944 KB Output is correct
8 Failed 6 ms 1160 KB Expected integer, but "prog2:" found (Baijan)
9 Halted 0 ms 0 KB -