Submission #122940

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
122940	2019-06-29T15:29:40 Z	atoiz	Two Transportations (JOI19_transportations)	C++14	100 / 100	1852 ms	85288 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1026 ms	1472 KB	Output is correct
2	Correct	6 ms	992 KB	Output is correct
3	Correct	938 ms	1504 KB	Output is correct
4	Correct	1292 ms	20080 KB	Output is correct
5	Correct	52 ms	1624 KB	Output is correct
6	Correct	1064 ms	4328 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1248 KB	Output is correct
2	Correct	854 ms	1760 KB	Output is correct
3	Correct	1030 ms	1536 KB	Output is correct
4	Correct	1316 ms	55064 KB	Output is correct
5	Correct	1552 ms	48480 KB	Output is correct
6	Correct	212 ms	1136 KB	Output is correct
7	Correct	1268 ms	48336 KB	Output is correct

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	868 ms	1768 KB	Output is correct
2	Correct	6 ms	1128 KB	Output is correct
3	Correct	1066 ms	1456 KB	Output is correct
4	Correct	938 ms	1600 KB	Output is correct
5	Correct	1125 ms	1592 KB	Output is correct
6	Correct	1142 ms	1624 KB	Output is correct
7	Correct	966 ms	1576 KB	Output is correct
8	Correct	786 ms	1504 KB	Output is correct
9	Correct	922 ms	1504 KB	Output is correct
10	Correct	988 ms	1536 KB	Output is correct

Subtask #4

38.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	1504 KB	Output is correct
2	Correct	442 ms	1320 KB	Output is correct
3	Correct	622 ms	23576 KB	Output is correct
4	Correct	384 ms	1560 KB	Output is correct
5	Correct	630 ms	17288 KB	Output is correct
6	Correct	246 ms	1760 KB	Output is correct
7	Correct	432 ms	1760 KB	Output is correct
8	Correct	480 ms	1504 KB	Output is correct
9	Correct	804 ms	36008 KB	Output is correct
10	Correct	766 ms	35856 KB	Output is correct
11	Correct	930 ms	61192 KB	Output is correct
12	Correct	982 ms	53376 KB	Output is correct
13	Correct	464 ms	1576 KB	Output is correct
14	Correct	6 ms	1384 KB	Output is correct

Subtask #5

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	1504 KB	Output is correct
2	Correct	442 ms	1320 KB	Output is correct
3	Correct	622 ms	23576 KB	Output is correct
4	Correct	384 ms	1560 KB	Output is correct
5	Correct	630 ms	17288 KB	Output is correct
6	Correct	246 ms	1760 KB	Output is correct
7	Correct	432 ms	1760 KB	Output is correct
8	Correct	480 ms	1504 KB	Output is correct
9	Correct	804 ms	36008 KB	Output is correct
10	Correct	766 ms	35856 KB	Output is correct
11	Correct	930 ms	61192 KB	Output is correct
12	Correct	982 ms	53376 KB	Output is correct
13	Correct	464 ms	1576 KB	Output is correct
14	Correct	6 ms	1384 KB	Output is correct
15	Correct	526 ms	1336 KB	Output is correct
16	Correct	524 ms	1344 KB	Output is correct
17	Correct	526 ms	1504 KB	Output is correct
18	Correct	762 ms	17504 KB	Output is correct
19	Correct	473 ms	1760 KB	Output is correct
20	Correct	632 ms	18096 KB	Output is correct
21	Correct	588 ms	1600 KB	Output is correct
22	Correct	524 ms	1504 KB	Output is correct
23	Correct	764 ms	44192 KB	Output is correct
24	Correct	990 ms	43712 KB	Output is correct
25	Correct	1146 ms	75072 KB	Output is correct
26	Correct	1124 ms	64248 KB	Output is correct
27	Correct	550 ms	1624 KB	Output is correct

Subtask #6

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	1504 KB	Output is correct
2	Correct	442 ms	1320 KB	Output is correct
3	Correct	622 ms	23576 KB	Output is correct
4	Correct	384 ms	1560 KB	Output is correct
5	Correct	630 ms	17288 KB	Output is correct
6	Correct	246 ms	1760 KB	Output is correct
7	Correct	432 ms	1760 KB	Output is correct
8	Correct	480 ms	1504 KB	Output is correct
9	Correct	804 ms	36008 KB	Output is correct
10	Correct	766 ms	35856 KB	Output is correct
11	Correct	930 ms	61192 KB	Output is correct
12	Correct	982 ms	53376 KB	Output is correct
13	Correct	464 ms	1576 KB	Output is correct
14	Correct	6 ms	1384 KB	Output is correct
15	Correct	526 ms	1336 KB	Output is correct
16	Correct	524 ms	1344 KB	Output is correct
17	Correct	526 ms	1504 KB	Output is correct
18	Correct	762 ms	17504 KB	Output is correct
19	Correct	473 ms	1760 KB	Output is correct
20	Correct	632 ms	18096 KB	Output is correct
21	Correct	588 ms	1600 KB	Output is correct
22	Correct	524 ms	1504 KB	Output is correct
23	Correct	764 ms	44192 KB	Output is correct
24	Correct	990 ms	43712 KB	Output is correct
25	Correct	1146 ms	75072 KB	Output is correct
26	Correct	1124 ms	64248 KB	Output is correct
27	Correct	550 ms	1624 KB	Output is correct
28	Correct	692 ms	1760 KB	Output is correct
29	Correct	758 ms	1504 KB	Output is correct
30	Correct	1074 ms	41936 KB	Output is correct
31	Correct	558 ms	1504 KB	Output is correct
32	Correct	926 ms	37576 KB	Output is correct
33	Correct	688 ms	1560 KB	Output is correct
34	Correct	734 ms	1632 KB	Output is correct
35	Correct	770 ms	1640 KB	Output is correct
36	Correct	1142 ms	48952 KB	Output is correct
37	Correct	1014 ms	49296 KB	Output is correct
38	Correct	1528 ms	85288 KB	Output is correct
39	Correct	1332 ms	78296 KB	Output is correct
40	Correct	654 ms	1880 KB	Output is correct

Subtask #7

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1026 ms	1472 KB	Output is correct
2	Correct	6 ms	992 KB	Output is correct
3	Correct	938 ms	1504 KB	Output is correct
4	Correct	1292 ms	20080 KB	Output is correct
5	Correct	52 ms	1624 KB	Output is correct
6	Correct	1064 ms	4328 KB	Output is correct
7	Correct	7 ms	1248 KB	Output is correct
8	Correct	854 ms	1760 KB	Output is correct
9	Correct	1030 ms	1536 KB	Output is correct
10	Correct	1316 ms	55064 KB	Output is correct
11	Correct	1552 ms	48480 KB	Output is correct
12	Correct	212 ms	1136 KB	Output is correct
13	Correct	1268 ms	48336 KB	Output is correct
14	Correct	868 ms	1768 KB	Output is correct
15	Correct	6 ms	1128 KB	Output is correct
16	Correct	1066 ms	1456 KB	Output is correct
17	Correct	938 ms	1600 KB	Output is correct
18	Correct	1125 ms	1592 KB	Output is correct
19	Correct	1142 ms	1624 KB	Output is correct
20	Correct	966 ms	1576 KB	Output is correct
21	Correct	786 ms	1504 KB	Output is correct
22	Correct	922 ms	1504 KB	Output is correct
23	Correct	988 ms	1536 KB	Output is correct
24	Correct	382 ms	1504 KB	Output is correct
25	Correct	442 ms	1320 KB	Output is correct
26	Correct	622 ms	23576 KB	Output is correct
27	Correct	384 ms	1560 KB	Output is correct
28	Correct	630 ms	17288 KB	Output is correct
29	Correct	246 ms	1760 KB	Output is correct
30	Correct	432 ms	1760 KB	Output is correct
31	Correct	480 ms	1504 KB	Output is correct
32	Correct	804 ms	36008 KB	Output is correct
33	Correct	766 ms	35856 KB	Output is correct
34	Correct	930 ms	61192 KB	Output is correct
35	Correct	982 ms	53376 KB	Output is correct
36	Correct	464 ms	1576 KB	Output is correct
37	Correct	6 ms	1384 KB	Output is correct
38	Correct	526 ms	1336 KB	Output is correct
39	Correct	524 ms	1344 KB	Output is correct
40	Correct	526 ms	1504 KB	Output is correct
41	Correct	762 ms	17504 KB	Output is correct
42	Correct	473 ms	1760 KB	Output is correct
43	Correct	632 ms	18096 KB	Output is correct
44	Correct	588 ms	1600 KB	Output is correct
45	Correct	524 ms	1504 KB	Output is correct
46	Correct	764 ms	44192 KB	Output is correct
47	Correct	990 ms	43712 KB	Output is correct
48	Correct	1146 ms	75072 KB	Output is correct
49	Correct	1124 ms	64248 KB	Output is correct
50	Correct	550 ms	1624 KB	Output is correct
51	Correct	692 ms	1760 KB	Output is correct
52	Correct	758 ms	1504 KB	Output is correct
53	Correct	1074 ms	41936 KB	Output is correct
54	Correct	558 ms	1504 KB	Output is correct
55	Correct	926 ms	37576 KB	Output is correct
56	Correct	688 ms	1560 KB	Output is correct
57	Correct	734 ms	1632 KB	Output is correct
58	Correct	770 ms	1640 KB	Output is correct
59	Correct	1142 ms	48952 KB	Output is correct
60	Correct	1014 ms	49296 KB	Output is correct
61	Correct	1528 ms	85288 KB	Output is correct
62	Correct	1332 ms	78296 KB	Output is correct
63	Correct	654 ms	1880 KB	Output is correct
64	Correct	938 ms	1880 KB	Output is correct
65	Correct	1530 ms	46992 KB	Output is correct
66	Correct	1326 ms	40896 KB	Output is correct
67	Correct	1050 ms	1928 KB	Output is correct
68	Correct	952 ms	1728 KB	Output is correct
69	Correct	1793 ms	83152 KB	Output is correct
70	Correct	1852 ms	67880 KB	Output is correct
71	Correct	1096 ms	8920 KB	Output is correct
72	Correct	865 ms	2464 KB	Output is correct