Submission #134864

#	Time	Username	Problem	Language	Result	Execution time	Memory
134864		scanhex	Two Transportations (JOI19_transportations)	C++17	100 / 100	1930 ms	85344 KiB

Azer

#include<bits/stdc++.h>
using namespace std;
#include "Azer.h"

namespace {
const int N=2020;
const int SZ=9;
vector<pair<int,int>>g[N];
deque<int>q;
void send(int x,int len){
	if(len==SZ)x=min(x,(1<<SZ)-1);
	for(int i=len-1;i>=0;--i)
		SendA(x>>i&1);
}
int receive(int len){
	assert(q.size()>=len);
	int ans=0;
	for(int i=0;i<len;++i)
		ans*=2,ans+=q.front(),q.pop_front();
	return ans;
}
int d[N];
int n;
const int oo=(1<<SZ)-1;
int state=0;
int rest=0;
int kek,mem;
auto cmp=[&](const int a,const int b){
	if(d[a]!=d[b])
		return d[a]<d[b];
	return a<b;
};
set<int,decltype(cmp)>st(cmp);
int last=0;
void relax(){
//	cerr<<"a "<<kek<<' '<<mem<<'\n';
	st.erase(kek);
	d[kek]=mem;
	last=mem;
	for(auto& [a,b]:g[kek]){
		if(d[kek]+b<d[a]){
			st.erase(a);
			d[a]=d[kek]+b;
			st.insert(a);
		}
	}
}
void proc(){
	int num=0;
	for(int x:q)num*=2,num+=x;
	q.clear();
	if(!st.size())return;
	if(state==0){
		kek=*st.begin();
		mem=d[kek];
//		cerr<<"a "<<mem<<'\n';
		send(mem-last,SZ);
		state=1;
		rest=SZ;
		return;
	}
	if(state==1){
		if(num==mem-last){
			send(kek,11);
			relax();
			state=0;
			proc();
			return;
		}
		else{
			mem=num+last;
			state=3;
			rest=11;
			return;
		}
	}
	if(state==3){
		kek=num;
		relax();
		state=0;
		proc();
		return;
	}
}
}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
		std::vector<int> C) {
	n=N;
	for(int i=0;i<A;++i){
		g[U[i]].emplace_back(V[i],C[i]);
		g[V[i]].emplace_back(U[i],C[i]);
	}
	fill(d,d+n,1<<20);
	d[0]=0;
	for(int i=0;i<n;++i)st.insert(i);
	proc();
}

void ReceiveA(bool x) {
	q.push_back(x);
	if(--rest==0){
		proc();
	}
}

std::vector<int> Answer() {
	vector<int>ans(d,d+n);
	return ans;
}

Baijan

#include<bits/stdc++.h>
using namespace std;
#include "Baijan.h"

namespace {
const int N=2020;
const int SZ=9;
vector<pair<int,int>>g[N];
deque<int>q;
void send(int x,int len){
	if(len==SZ)x=min(x,(1<<SZ)-1);
	for(int i=len-1;i>=0;--i)
		SendB(x>>i&1);
}
int receive(int len){
	assert(q.size()>=len);
	int ans=0;
	for(int i=0;i<len;++i)
		ans*=2,ans+=q.front(),q.pop_front();
	return ans;
}
int d[N];
int n;
const int oo=(1<<SZ)-1;
int rest=0;
int state=0;
int kek,mem;
auto cmp=[&](const int a,const int b){
	if(d[a]!=d[b])
		return d[a]<d[b];
	return a<b;
};
set<int,decltype(cmp)>st(cmp);
int last=0;
void relax(){
//	cerr<<kek<<' '<<mem<<'\n';
	st.erase(kek);
	d[kek]=mem;
	last=mem;
	for(auto& [a,b]:g[kek]){
		if(d[kek]+b<d[a]){
			st.erase(a);
			d[a]=d[kek]+b;
			st.insert(a);
		}
	}
}

void proc(){
	int num=0;
	for(int x:q)num*=2,num+=x;
	q.clear();
//	cerr<<num<<'\n';
	if(!st.size())return;
	if(state==0){
		kek=*st.begin();
		mem=d[kek];
		int di=num+last;
//		cerr<<di<<'\n';
		if(mem>=di){
			send(num,SZ);
			mem=di;
			state=1;
			rest=11;
			return;
		}
		else{
//			cerr<<"rofl\n";
			send(mem-last,SZ);
			send(kek,11);
			state=0;
			rest=SZ;
			relax();
			return;
		}
	}
	if(state==1){
		kek=num;
		relax();
		state=0;
		rest=SZ;
		return;
	}
}
}  // namespace

void InitB(int N, int B, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
	n=N;
	for(int i=0;i<B;++i){
		g[U[i]].emplace_back(V[i],C[i]);
		g[V[i]].emplace_back(U[i],C[i]);
	}
	fill(d,d+n,1<<20);
	d[0]=0;
	for(int i=0;i<n;++i)st.insert(i);
	rest=SZ;
}


void ReceiveB(bool y) {
	q.push_back(y);
	if(--rest==0)proc();
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Azer.cpp:1:
Azer.cpp: In function 'int {anonymous}::receive(int)':
Azer.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(q.size()>=len);
         ~~~~~~~~^~~
Azer.cpp: At global scope:
Azer.cpp:15:5: warning: 'int {anonymous}::receive(int)' defined but not used [-Wunused-function]
 int receive(int len){
     ^~~~~~~

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from Baijan.cpp:1:
Baijan.cpp: In function 'int {anonymous}::receive(int)':
Baijan.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(q.size()>=len);
         ~~~~~~~~^~~
Baijan.cpp: At global scope:
Baijan.cpp:15:5: warning: 'int {anonymous}::receive(int)' defined but not used [-Wunused-function]
 int receive(int len){
     ^~~~~~~

• 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