oj.uz

Submission #123347

# Submission time Handle Problem Language Result Execution time Memory
123347 2019-07-01T07:53:03 Z 임유진(#3021) Two Transportations (JOI19_transportations) C++14
0 / 100
 1516 ms 72464 KB 
#include "Azer.h"
#include <vector>
#include <queue>

#define MAXN 2005

typedef std::pair<int, int> pii;

namespace {

int N;
int count;
int node, dis;
int dp[MAXN], dpn;
std::vector<pii> ed[MAXN];
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > pq;
int lastdis;

void send() {
	if(pq.empty()) {
		for(int i = 0; i < 20; i++) SendA(false);
		//printf("A: node = 0, dis = 0\n");
	}
	else{
		for(int i = 0; i < 11; i++) SendA(pq.top().second & (1<<i) ? true : false);
		for(int i = 0; i < 9; i++) SendA((pq.top().first - lastdis) & (1<<i) ? true : false);
		//printf("A: node = %d, dis = %d\n", pq.top().second, (pq.top().first - lastdis));
	}
}

}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	//printf("*\n");
	::N = N;
	for(int i = 0; i < U.size(); i++) {
		ed[U[i]].push_back(std::make_pair(C[i], V[i]));
		ed[V[i]].push_back(std::make_pair(C[i], U[i]));
	}
	for(int i = 0; i < N; i++) dp[i] = -1;
	dp[0] = 0;
	for(auto a : ed[0]) pq.push(a);
	send();
}

void ReceiveA(bool x) {
	if(x) {
		if(count < 11) node += 1 << count;
		else dis += 1 << (count - 11);
	}
	count++;
	if(count == 20) {
		count = 0;
		dp[node] = lastdis + dis;
		lastdis = dp[node];
		//printf("A: dp[%d] = %d\n", node, dp[node]);
		for(auto a : ed[node]) if(dp[a.second] == -1) pq.push(std::make_pair(dp[node] + a.first, a.second));
		while(!pq.empty() && dp[pq.top().second] != -1) pq.pop();
		//if(pq.empty()) printf("A: pq empty\n");
		//else printf("A: pq.top() = (%d, %d)\n", pq.top().first, pq.top().second);
		if(++dpn < N-1) send();
		node = dis = 0;
	}
}

std::vector<int> Answer() {
	std::vector<int> ans(N);
	for(int i = 0; i < N; i++) ans[i] = dp[i];
	return ans;
}

#include "Baijan.h"
#include <vector>
#include <queue>

#define MAXN 2005

typedef std::pair<int, int> pii;

namespace{

int count;
int node, dis;
int dp[MAXN];
std::vector<pii> ed[MAXN];
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > pq;
int lastdis;

void send(int a, int b) {
	for(int i = 0; i < 11; i++) SendB(a & (1<<i) ? true : false);
	for(int i = 0; i < 9; i++) SendB(b & (1<<i) ? true : false);
	//printf("B: node = %d, dis = %d\n", a, b);
}

}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
	for(int i = 0; i < S.size(); i++) {
		ed[S[i]].push_back(std::make_pair(D[i], T[i]));
		ed[T[i]].push_back(std::make_pair(D[i], S[i]));
	}
	for(int i = 0; i < N; i++) dp[i] = -1;
	dp[0] = 0;
	for(auto a : ed[0]) pq.push(a);
}

void ReceiveB(bool y) {
	if(y) {
		if(count < 11) node += 1 << count;
		else dis += 1 << (count - 11);
	}
	count++;
	if(count == 20) {
		count = 0;
		while(!pq.empty() && dp[pq.top().second] != -1) pq.pop();
		//if(pq.empty()) printf("B: pq empty\n");
		//else printf("B: pq.top() = (%d, %d)\n", pq.top().first, pq.top().second);
		if(node != 0 && (pq.empty() || lastdis + dis < pq.top().first)) {
			dp[node] = lastdis + dis;
			for(auto a : ed[node]) if(dp[a.second] == -1) pq.push(std::make_pair(dp[node] + a.first, a.second));
			send(node, dp[node] - lastdis);
			lastdis = dp[node];
		}
		else {
			//printf("B*\n");
			dp[pq.top().second] = pq.top().first;
			send(pq.top().second, pq.top().first - lastdis);
			lastdis = pq.top().first;
			for(auto a : ed[pq.top().second]) if(dp[a.second] == -1) pq.push(std::make_pair(dp[pq.top().second] + a.first, a.second));
		}
		node = dis = 0;
	}
}

Compilation message

Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++) {
                 ~~^~~~~~~~~~

Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < S.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Failed 3 ms 760 KB Unexpected end of file - int32 expected (Baijan)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 1256 KB Output is correct
2 Correct 546 ms 1296 KB Output is correct
3 Correct 994 ms 23472 KB Output is correct
4 Correct 546 ms 1328 KB Output is correct
5 Correct 946 ms 17216 KB Output is correct
6 Correct 708 ms 1456 KB Output is correct
7 Correct 600 ms 1600 KB Output is correct
8 Correct 614 ms 1504 KB Output is correct
9 Correct 1150 ms 39048 KB Output is correct
10 Correct 968 ms 38856 KB Output is correct
11 Correct 1516 ms 72464 KB Output is correct
12 Correct 1208 ms 67320 KB Output is correct
13 Correct 528 ms 1392 KB Output is correct
14 Failed 5 ms 768 KB Unexpected end of file - int32 expected (Baijan)

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 1256 KB Output is correct
2 Correct 546 ms 1296 KB Output is correct
3 Correct 994 ms 23472 KB Output is correct
4 Correct 546 ms 1328 KB Output is correct
5 Correct 946 ms 17216 KB Output is correct
6 Correct 708 ms 1456 KB Output is correct
7 Correct 600 ms 1600 KB Output is correct
8 Correct 614 ms 1504 KB Output is correct
9 Correct 1150 ms 39048 KB Output is correct
10 Correct 968 ms 38856 KB Output is correct
11 Correct 1516 ms 72464 KB Output is correct
12 Correct 1208 ms 67320 KB Output is correct
13 Correct 528 ms 1392 KB Output is correct
14 Failed 5 ms 768 KB Unexpected end of file - int32 expected (Baijan)

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 1256 KB Output is correct
2 Correct 546 ms 1296 KB Output is correct
3 Correct 994 ms 23472 KB Output is correct
4 Correct 546 ms 1328 KB Output is correct
5 Correct 946 ms 17216 KB Output is correct
6 Correct 708 ms 1456 KB Output is correct
7 Correct 600 ms 1600 KB Output is correct
8 Correct 614 ms 1504 KB Output is correct
9 Correct 1150 ms 39048 KB Output is correct
10 Correct 968 ms 38856 KB Output is correct
11 Correct 1516 ms 72464 KB Output is correct
12 Correct 1208 ms 67320 KB Output is correct
13 Correct 528 ms 1392 KB Output is correct
14 Failed 5 ms 768 KB Unexpected end of file - int32 expected (Baijan)

Subtask #7
0 / 16.0

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