oj.uz

답안 #152840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152840 2019-09-10T00:11:46 Z username Two Transportations (JOI19_transportations) C++14
38 / 100
 2226 ms 61096 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1010 ms 1328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1248 KB Output is correct
2 Incorrect 901 ms 1420 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1020 ms 1304 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 2192 KB Output is correct
2 Correct 1237 ms 1872 KB Output is correct
3 Correct 1820 ms 23560 KB Output is correct
4 Correct 1302 ms 2416 KB Output is correct
5 Correct 1614 ms 17144 KB Output is correct
6 Correct 708 ms 2248 KB Output is correct
7 Correct 856 ms 2392 KB Output is correct
8 Correct 832 ms 2272 KB Output is correct
9 Correct 1734 ms 35920 KB Output is correct
10 Correct 1830 ms 35816 KB Output is correct
11 Correct 2226 ms 61096 KB Output is correct
12 Correct 1430 ms 54024 KB Output is correct
13 Correct 670 ms 2152 KB Output is correct
14 Correct 8 ms 936 KB Output is correct

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 2192 KB Output is correct
2 Correct 1237 ms 1872 KB Output is correct
3 Correct 1820 ms 23560 KB Output is correct
4 Correct 1302 ms 2416 KB Output is correct
5 Correct 1614 ms 17144 KB Output is correct
6 Correct 708 ms 2248 KB Output is correct
7 Correct 856 ms 2392 KB Output is correct
8 Correct 832 ms 2272 KB Output is correct
9 Correct 1734 ms 35920 KB Output is correct
10 Correct 1830 ms 35816 KB Output is correct
11 Correct 2226 ms 61096 KB Output is correct
12 Correct 1430 ms 54024 KB Output is correct
13 Correct 670 ms 2152 KB Output is correct
14 Correct 8 ms 936 KB Output is correct
15 Correct 990 ms 2416 KB Output is correct
16 Incorrect 859 ms 1084 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 2192 KB Output is correct
2 Correct 1237 ms 1872 KB Output is correct
3 Correct 1820 ms 23560 KB Output is correct
4 Correct 1302 ms 2416 KB Output is correct
5 Correct 1614 ms 17144 KB Output is correct
6 Correct 708 ms 2248 KB Output is correct
7 Correct 856 ms 2392 KB Output is correct
8 Correct 832 ms 2272 KB Output is correct
9 Correct 1734 ms 35920 KB Output is correct
10 Correct 1830 ms 35816 KB Output is correct
11 Correct 2226 ms 61096 KB Output is correct
12 Correct 1430 ms 54024 KB Output is correct
13 Correct 670 ms 2152 KB Output is correct
14 Correct 8 ms 936 KB Output is correct
15 Correct 990 ms 2416 KB Output is correct
16 Incorrect 859 ms 1084 KB Wrong Answer [2]
17 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1010 ms 1328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -