oj.uz

Submission #132363

# Submission time Handle Problem Language Result Execution time Memory
132363 2019-07-18T18:28:47 Z sebinkim Two Transportations (JOI19_transportations) C++14
38 / 100
 1463 ms 61144 KB 
#include <bits/stdc++.h>

#include "Azer.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 20;

namespace{
	priority_queue <pii> Q;
	vector <pii> G[2020];
	vector <int> D;
	bool chk[2020];
	int _st, _val, _cnt;
	int n;
}

static void sendint(int x, int l) { for(; l--; ) SendA((x & (1 << l))? 1 : 0); }

static void apply(int p, int d)
{
//	printf("applyA %d %d\n", p, d);
	chk[p] = 1; D[p] = d;
	
	for(pii &t: G[p]){
		if(!chk[t.first] && D[t.first] > d + t.second){
			D[t.first] = d + t.second;
			Q.emplace(-d - t.second, t.first);
		}
	}
}

static void check()
{
	int p, d;
	
	for(; !Q.empty(); Q.pop()){
		tie(d, p) = Q.top(); d = -d;
		if(!chk[p] && d == D[p]) break;
	}
	
	if(Q.empty()) return;
	
	_st = 0;
	
	tie(d, p) = Q.top(); d = -d;
	
	sendint(p, ID);
	sendint(d, DIST);
}

void InitA(int N, int A, vector <int> U, vector <int> V, vector<int> C)
{
	n = N; D.resize(n, 0);
	
	int i;
	
	for(i=0; i<A; i++){
		G[U[i]].emplace_back(V[i], C[i]);
		G[V[i]].emplace_back(U[i], C[i]);
	}
	
	for(i=1; i<n; i++){
		D[i] = (1 << DIST) - 1;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
	check();
}

void ReceiveA(bool x)
{
//	printf("ReceiveA %d\n", x);
	if(!_st){
		if(!x){
			int d, p;
			tie(d, p) = Q.top();
			d = -d; Q.pop();
			apply(p, d); check();
		}
		else _st = 1;
	}
	else{
		_val = _val << 1 | x; _cnt ++;
	
		if(_cnt == ID + DIST){
			int p = _val >> DIST;
			int d = _val & ((1 << DIST) - 1);
			_val = 0; _cnt = 0; _st = 0;
			apply(p, d); check();
		}
	}
}

vector <int> Answer() { return D; }
#include <bits/stdc++.h>

#include "Baijan.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 20;

namespace{
	priority_queue <pii> Q;
	vector <pii> G[2020];
	vector <int> D;
	bool chk[2020];
	int _st, _val, _cnt;
	int n;
}

static void sendint(int x, int l) { for(; l--; ) SendB((x & (1 << l))? 1 : 0); }

static void apply(int p, int d)
{
//	printf("applyB %d %d\n", p, d);
	chk[p] = 1; D[p] = d;
	
	for(pii &t: G[p]){
		if(!chk[t.first] && D[t.first] > d + t.second){
			D[t.first] = d + t.second;
//			printf("updateB %d %d\n", t.first, d + t.second);
			Q.emplace(-d - t.second, t.first);
		}
	}
}

static void check(int pa, int da)
{
	int p, d, pb, db;
	
	for(; !Q.empty(); Q.pop()){
		tie(db, pb) = Q.top(); db = -db;
		if(!chk[pb] && D[pb] == db) break;
	}
	
	tie(db, pb) = Q.top(); db = -db;
	
	if(da < db){
		p = pa, d = da;
		SendB(0);
	}
	else{
		p = pb, d = db; Q.pop();
		SendB(1);
		sendint(p, ID);
		sendint(d, DIST);
	}
	
	apply(p, d);
}

void InitB(int N, int B, vector <int> S, vector<int> T, vector<int> C)
{
	n = N; D.resize(n, 0);
	
	int i;
	
	for(i=0; i<B; i++){
		G[S[i]].emplace_back(T[i], C[i]);
		G[T[i]].emplace_back(S[i], C[i]);
	}
	
	for(i=1; i<n; i++){
		D[i] = (1 << DIST) - 1;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
}

void ReceiveB(bool y)
{
//	printf("ReceiveB %d\n", y);
	_val = _val << 1 | y; _cnt ++;
	
	if(_cnt == ID + DIST){
		int p = _val >> DIST;
		int d = _val & ((1 << DIST) - 1);
		_val = 0; _cnt = 0;
		check(p, d);
	}
}

Compilation message

Baijan.cpp:17:6: warning: '{anonymous}::_st' defined but not used [-Wunused-variable]
  int _st, _val, _cnt;
      ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 932 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 1000 KB Output is correct
2 Incorrect 428 ms 996 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 1560 KB Output is correct
2 Correct 604 ms 1296 KB Output is correct
3 Correct 940 ms 23648 KB Output is correct
4 Correct 776 ms 1408 KB Output is correct
5 Correct 948 ms 17320 KB Output is correct
6 Correct 714 ms 1568 KB Output is correct
7 Correct 610 ms 1768 KB Output is correct
8 Correct 752 ms 1600 KB Output is correct
9 Correct 920 ms 36232 KB Output is correct
10 Correct 1218 ms 35848 KB Output is correct
11 Correct 1463 ms 61144 KB Output is correct
12 Correct 1168 ms 53616 KB Output is correct
13 Correct 516 ms 1688 KB Output is correct
14 Correct 8 ms 1224 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 1560 KB Output is correct
2 Correct 604 ms 1296 KB Output is correct
3 Correct 940 ms 23648 KB Output is correct
4 Correct 776 ms 1408 KB Output is correct
5 Correct 948 ms 17320 KB Output is correct
6 Correct 714 ms 1568 KB Output is correct
7 Correct 610 ms 1768 KB Output is correct
8 Correct 752 ms 1600 KB Output is correct
9 Correct 920 ms 36232 KB Output is correct
10 Correct 1218 ms 35848 KB Output is correct
11 Correct 1463 ms 61144 KB Output is correct
12 Correct 1168 ms 53616 KB Output is correct
13 Correct 516 ms 1688 KB Output is correct
14 Correct 8 ms 1224 KB Output is correct
15 Correct 627 ms 1416 KB Output is correct
16 Correct 560 ms 1504 KB Output is correct
17 Correct 614 ms 1560 KB Output is correct
18 Incorrect 460 ms 8764 KB Wrong Answer [2]
19 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 1560 KB Output is correct
2 Correct 604 ms 1296 KB Output is correct
3 Correct 940 ms 23648 KB Output is correct
4 Correct 776 ms 1408 KB Output is correct
5 Correct 948 ms 17320 KB Output is correct
6 Correct 714 ms 1568 KB Output is correct
7 Correct 610 ms 1768 KB Output is correct
8 Correct 752 ms 1600 KB Output is correct
9 Correct 920 ms 36232 KB Output is correct
10 Correct 1218 ms 35848 KB Output is correct
11 Correct 1463 ms 61144 KB Output is correct
12 Correct 1168 ms 53616 KB Output is correct
13 Correct 516 ms 1688 KB Output is correct
14 Correct 8 ms 1224 KB Output is correct
15 Correct 627 ms 1416 KB Output is correct
16 Correct 560 ms 1504 KB Output is correct
17 Correct 614 ms 1560 KB Output is correct
18 Incorrect 460 ms 8764 KB Wrong Answer [2]
19 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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