Submission #259483

#	Time	Username	Problem	Language	Result	Execution time	Memory
259483		dorijanlendvaj	Two Transportations (JOI19_transportations)	C++14	100 / 100	2580 ms	141176 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

namespace {
priority_queue<pii> pq;
const int N=300010;
int n,la,cn,curn,bn,res[N],ther;
vector<pii> ch[N];
bool bio[N];
bool expect11;
void send9(int num)
{
	num=min(num,511);
	vi v;
	for (int i=0;i<9;++i)
	{
		v.pb(num%2);
		num/=2;
	}
	reverse(all(v));
	for (auto a: v) SendA(a);
}

void send11(int num)
{
	num=min(num,2047);
	vi v;
	for (int i=0;i<11;++i)
	{
		v.pb(num%2);
		num/=2;
	}
	reverse(all(v));
	for (auto a: v) SendA(a);
}

void work(int num)
{
	while (bio[pq.top().y]) pq.pop();
	//cout<<"A "<<pq.top().x<<' '<<pq.top().y<<' '<<la<<endl;
	if (expect11)
	{
		la+=ther;
		res[num]=la;
		bio[num]=1;
		++bn;
		if (bn==n) return;
		for (auto a: ch[num]) pq.push({-res[num]-a.y,a.x});
		while (bio[pq.top().y]) pq.pop();
		expect11=0;
		send9(-pq.top().x-la);
	}
	else
	{
		int njre=num+la;
		int more=-pq.top().x;
		if (more<njre)
		{
			bio[pq.top().y]=1;
			res[pq.top().y]=more;
			++bn;
			for (auto a: ch[pq.top().y]) pq.push({-res[pq.top().y]-a.y,a.x});
			la=more;
			send11(pq.top().y);
			if (bn==n) return;
			while (bio[pq.top().y]) pq.pop();
			send9(-pq.top().x-la);
		}
		else expect11=1,ther=num;
	}
}
}


void InitA(int N, int A, vi U, vi V, vi C)
{
	n=N;
	for (int i=0;i<A;++i)
	{
		ch[U[i]].eb(V[i],C[i]);
		ch[V[i]].eb(U[i],C[i]);
	}
	for (int i=0;i<N;++i) pq.push({-MOD,2047});
	bio[0]=1;
	for (auto a: ch[0]) pq.push({-a.y,a.x});
	++bn;
	if (bn==n) return;
	send9(-pq.top().x-la);
}

void ReceiveA(bool x) {
  ++cn;
  curn=curn*2+x;
  if ((cn==9 && !expect11) || (cn==11 && expect11))
  {
  	//cout<<"A got number "<<curn<<endl;
  	work(curn);
  	curn=0;
  	cn=0;
  }
}

vi Answer() {
  vi ans(n);
  for (int k = 0; k < n; ++k) {
    ans[k] = res[k];
  }
  return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(a) begin(a),end(a)

using namespace std;

namespace {

priority_queue<pii> pq;
const int N=300010;
int n,la,cn,curn,res[N],ther;
vector<pii> ch[N];
bool bio[N];
bool expect11;
void send9(int num)
{
	num=min(num,511);
	vi v;
	for (int i=0;i<9;++i)
	{
		v.pb(num%2);
		num/=2;
	}
	reverse(all(v));
	for (auto a: v) SendB(a);
}

void send11(int num)
{
	num=min(num,2047);
	vi v;
	for (int i=0;i<11;++i)
	{
		v.pb(num%2);
		num/=2;
	}
	reverse(all(v));
	for (auto a: v) SendB(a);
}

void work(int num)
{
	while (bio[pq.top().y]) pq.pop();
	//cout<<"B "<<pq.top().x<<' '<<pq.top().y<<' '<<la<<endl;
	if (expect11)
	{
		la+=ther;
		res[num]=la;
		bio[num]=1;
		for (auto a: ch[num]) pq.push({-res[num]-a.y,a.x});
		while (bio[pq.top().y]) pq.pop();
		expect11=0;
		//send9(-pq.top().x-la);
	}
	else
	{
		int njre=num+la;
		int more=-pq.top().x;
		if (more<=njre)
		{
			bio[pq.top().y]=1;
			res[pq.top().y]=more;
			for (auto a: ch[pq.top().y]) pq.push({-res[pq.top().y]-a.y,a.x});
			send9(more-la);
			la=more;
			send11(pq.top().y);
			while (bio[pq.top().y]) pq.pop();
		}
		else
		{
			expect11=1;
			ther=num;
			send9(more-la);
		}
	}
}

}  // namespace

void InitB(int N, int A, vi U, vi V, vi C)
{
	n=N;
	for (int i=0;i<A;++i)
	{
		ch[U[i]].eb(V[i],C[i]);
		ch[V[i]].eb(U[i],C[i]);
	}
	for (int i=0;i<N;++i) pq.push({-1e9,2047});
	bio[0]=1;
	for (auto a: ch[0]) pq.push({-a.y,a.x});
}

void ReceiveB(bool y) {
  ++cn;
  curn=curn*2+y;
  if ((cn==9 && !expect11) || (cn==11 && expect11))
  {
  	//cout<<"B got number "<<curn<<endl;
  	work(curn);
  	curn=0;
  	cn=0;
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16