oj.uz

Submission #135525

# Submission time Handle Problem Language Result Execution time Memory
135525 2019-07-24T07:31:47 Z E869120 Two Transportations (JOI19_transportations) C++14
38 / 100
 1934 ms 60928 KB 
#include "Azer.h"
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
using namespace std;

int NA, distA[2009];
vector<pair<int, int>> XA[2009];
map<pair<int, int>, int> ForcedA;

void pushesA(int pos, int val) {
	// 最初の 11 ビットは頂点、次の 20 ビットはコスト
	for (int i = 0; i < 11; i++) SendA((bool)((pos / (1 << i)) % 2));
	for (int i = 0; i < 20; i++) SendA((bool)((val / (1 << i)) % 2));
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	NA = N;
	for (int i = 0; i < U.size(); i++) {
		XA[U[i]].push_back(make_pair(V[i], C[i]));
		XA[V[i]].push_back(make_pair(U[i], C[i]));
	}
	for (int i = 0; i < N; i++) distA[i] = (1 << 20) - 1;
	distA[0] = 0; ForcedA[make_pair(0, 0)] = 1;
	pushesA(0, 0);
	for (int i = 0; i < XA[0].size(); i++) distA[XA[0][i].first] = XA[0][i].second;
}

int countA = 0, VA = 0, LA = 0;

void ReceiveA(bool x) {
	if (countA < 31) {
		if (x == true) VA += (1 << countA);
		countA++;
	}
	if (countA == 31) {
		int pos = (VA & 2047), val = (VA >> 11);
		if (pos != 2047) {
			if (distA[pos] > val) {
				distA[pos] = val; if (val != 1048575) ForcedA[make_pair(distA[pos], pos)] = 1;
				for (int i = 0; i < XA[pos].size(); i++) {
					int to = XA[pos][i].first, cost = XA[pos][i].second;
					if (distA[to] > distA[pos] + cost) {
						distA[to] = distA[pos] + cost;
					}
				}
			}
		}

		pair<int, int> minid = make_pair(1 << 30, -1);
		for (int i = 0; i < NA; i++) {
			if (ForcedA[make_pair(distA[i], i)] == 0) minid = min(minid, make_pair(distA[i], i));
		}

		if (minid.second != -1) {
			pushesA(minid.second, minid.first); if (minid.first != 1048575) ForcedA[minid] = 1;

			for (int i = 0; i < XA[minid.second].size(); i++) {
				int to = XA[minid.second][i].first, cost = XA[minid.second][i].second;
				if (distA[to] > minid.first + cost) {
					distA[to] = minid.first + cost;
				}
			}
		}
		else if (pos != 2047) {
			pushesA(2047, 1048575);
		}
	}
	if (countA == 31) { countA = 0; VA = 0; }
}

vector<int> Answer() {
	vector<int>E;
	for (int i = 0; i < NA; i++) E.push_back(distA[i]);
	return E;
}

#include "Baijan.h"
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
using namespace std;

int NB, distB[2009];
vector<pair<int, int>> XB[2009];
map<pair<int, int>, int> ForcedB;
bool usedB[2009];

void pushesB(int pos, int val) {
	// 最初の 11 ビットは頂点、次の 20 ビットはコスト
	for (int i = 0; i < 11; i++) SendB((bool)((pos / (1 << i)) % 2));
	for (int i = 0; i < 20; i++) SendB((bool)((val / (1 << i)) % 2));
}

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
	NB = N;
	for (int i = 0; i < S.size(); i++) {
		XB[S[i]].push_back(make_pair(T[i], D[i]));
		XB[T[i]].push_back(make_pair(S[i], D[i]));
	}
	for (int i = 0; i < N; i++) distB[i] = (1 << 20) - 1;
	distB[0] = 0;
	for (int i = 0; i < XB[0].size(); i++) distB[XB[0][i].first] = XB[0][i].second;
	ForcedB[make_pair(0, 0)] = 1;
}

int countB = 0, VB = 0;

void ReceiveB(bool y) {
	if (countB < 31) {
		if (y == true) VB += (1 << countB);
		countB++;
	}
	if (countB == 31) {
		int pos = (VB & 2047), val = (VB >> 11);
		if (pos != 2047) {
			if (distB[pos] > val) {
				distB[pos] = val; if (val != 1048575) ForcedB[make_pair(distB[pos], pos)] = 1;
				for (int i = 0; i < XB[pos].size(); i++) {
					int to = XB[pos][i].first, cost = XB[pos][i].second;
					if (distB[to] > distB[pos] + cost) {
						distB[to] = distB[pos] + cost;
					}
				}
			}
		}

		pair<int, int> minid = make_pair(1 << 30, -1);
		for (int i = 0; i < NB; i++) {
			if (ForcedB[make_pair(distB[i], i)] == 0) minid = min(minid, make_pair(distB[i], i));
		}

		if (minid.second != -1) {
			pushesB(minid.second, minid.first); if (minid.first != 1048575) ForcedB[minid] = 1;

			for (int i = 0; i < XB[minid.second].size(); i++) {
				int to = XB[minid.second][i].first, cost = XB[minid.second][i].second;
				if (distB[to] > minid.first + cost) {
					distB[to] = minid.first + cost;
				}
			}
		}
		else if (pos != 2047) {
			pushesB(2047, 1048575);
		}
	}
	if (countB == 31) { countB = 0; VB = 0; }
}

Compilation message

Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < U.size(); i++) {
                  ~~^~~~~~~~~~
Azer.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < XA[0].size(); i++) distA[XA[0][i].first] = XA[0][i].second;
                  ~~^~~~~~~~~~~~~~
Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < XA[pos].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
Azer.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < XA[minid.second].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
Baijan.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < XB[0].size(); i++) distB[XB[0][i].first] = XB[0][i].second;
                  ~~^~~~~~~~~~~~~~
Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < XB[pos].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~
Baijan.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < XB[minid.second].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 960 KB Output is correct
2 Incorrect 1002 ms 1292 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 1968 KB Output is correct
2 Correct 954 ms 1808 KB Output is correct
3 Correct 1590 ms 23496 KB Output is correct
4 Correct 1066 ms 2424 KB Output is correct
5 Correct 1573 ms 17264 KB Output is correct
6 Correct 692 ms 1984 KB Output is correct
7 Correct 718 ms 2456 KB Output is correct
8 Correct 678 ms 2192 KB Output is correct
9 Correct 1440 ms 36000 KB Output is correct
10 Correct 1662 ms 35768 KB Output is correct
11 Correct 1934 ms 60928 KB Output is correct
12 Correct 1442 ms 53800 KB Output is correct
13 Correct 728 ms 2120 KB Output is correct
14 Correct 6 ms 1192 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 1968 KB Output is correct
2 Correct 954 ms 1808 KB Output is correct
3 Correct 1590 ms 23496 KB Output is correct
4 Correct 1066 ms 2424 KB Output is correct
5 Correct 1573 ms 17264 KB Output is correct
6 Correct 692 ms 1984 KB Output is correct
7 Correct 718 ms 2456 KB Output is correct
8 Correct 678 ms 2192 KB Output is correct
9 Correct 1440 ms 36000 KB Output is correct
10 Correct 1662 ms 35768 KB Output is correct
11 Correct 1934 ms 60928 KB Output is correct
12 Correct 1442 ms 53800 KB Output is correct
13 Correct 728 ms 2120 KB Output is correct
14 Correct 6 ms 1192 KB Output is correct
15 Correct 862 ms 1760 KB Output is correct
16 Incorrect 756 ms 980 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 1968 KB Output is correct
2 Correct 954 ms 1808 KB Output is correct
3 Correct 1590 ms 23496 KB Output is correct
4 Correct 1066 ms 2424 KB Output is correct
5 Correct 1573 ms 17264 KB Output is correct
6 Correct 692 ms 1984 KB Output is correct
7 Correct 718 ms 2456 KB Output is correct
8 Correct 678 ms 2192 KB Output is correct
9 Correct 1440 ms 36000 KB Output is correct
10 Correct 1662 ms 35768 KB Output is correct
11 Correct 1934 ms 60928 KB Output is correct
12 Correct 1442 ms 53800 KB Output is correct
13 Correct 728 ms 2120 KB Output is correct
14 Correct 6 ms 1192 KB Output is correct
15 Correct 862 ms 1760 KB Output is correct
16 Incorrect 756 ms 980 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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