oj.uz

Submission #132365

# Submission time Handle Problem Language Result Execution time Memory
132365 2019-07-18T18:35:07 Z sebinkim Two Transportations (JOI19_transportations) C++14
0 / 100
 634 ms 1504 KB 
#include <bits/stdc++.h>

#include "Azer.h"

using namespace std;

typedef pair <int, int> pii;

const int ID = 11;
const int DIST = 9;

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

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

static void apply(int p, int d)
{
	chk[p] = 1; D[p] = d; z = 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 - z, 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] = 1e9;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
	check();
}

void ReceiveA(bool 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 = z + (_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 = 9;

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

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

static void apply(int p, int d)
{
	chk[p] = 1; D[p] = d; z = 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 pa, int da)
{
	int p, d, pb, db;
	
	da += z;
	
	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 - z, 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] = 1e9;
	}
	
	for(i=0; i<n; i++){
		Q.emplace(-D[i], i);
	}
	
	apply(0, 0);
}

void ReceiveB(bool y)
{
	_val = _val << 1 | y; _cnt ++;
	
	if(_cnt == ID + DIST){
		int p = _val >> DIST;
		int d = z + (_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 511 ms 804 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 1248 KB Output is correct
2 Incorrect 550 ms 900 KB Wrong Answer [2]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 634 ms 1504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 634 ms 1504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 634 ms 1504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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