oj.uz

답안 #122933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122933 2019-06-29T15:08:31 Z atoiz Two Transportations (JOI19_transportations) C++14
6 / 100
 1492 ms 20128 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 = dist[nxtU];

		if (wA < wB) {
			lastW = wA;
			state = VERTEX;
		} else {
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 1496 KB Output is correct
2 Correct 8 ms 1080 KB Output is correct
3 Correct 966 ms 1536 KB Output is correct
4 Correct 1492 ms 20128 KB Output is correct
5 Correct 52 ms 1528 KB Output is correct
6 Correct 1070 ms 4560 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1248 KB Output is correct
2 Failed 5 ms 1376 KB Unexpected end of file - int32 expected (Baijan)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Failed 551 ms 1004 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Failed 188 ms 904 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Failed 188 ms 904 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Failed 188 ms 904 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 1496 KB Output is correct
2 Correct 8 ms 1080 KB Output is correct
3 Correct 966 ms 1536 KB Output is correct
4 Correct 1492 ms 20128 KB Output is correct
5 Correct 52 ms 1528 KB Output is correct
6 Correct 1070 ms 4560 KB Output is correct
7 Correct 6 ms 1248 KB Output is correct
8 Failed 5 ms 1376 KB Unexpected end of file - int32 expected (Baijan)
9 Halted 0 ms 0 KB -