제출 #122940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122940		atoiz	Two Transportations (JOI19_transportations)	C++14	100 / 100	1852 ms	85288 KiB

Azer

#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) {
			// cerr << "A " << nxtU << ' ' << wA << ' ' << wB << endl;
			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; }

Baijan

#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 {
			// cerr << "B " << nxtU << ' ' << wA << ' ' << wB << endl;
			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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16