Submission #1220124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220124		emptypringlescan	Two Transportations (JOI19_transportations)	C++17	100 / 100	351 ms	49720 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
	int n;
	vector<pair<int,int> > adj[2005];
	int v[2005];
	int d[2005];
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	vector<int> recv;
	int phase,beeg;
	pair<int,int> mine;
	int got;
	void loose(int x, int d){
		for(auto i:adj[x]){
			if(v[i.first]) continue;
			pq.push({d+i.second,i.first});
		}
		phase=0;
		bool have=false;
		while(!pq.empty()){
			int a=pq.top().first,b=pq.top().second;
			mine={a-beeg,b};
			pq.pop();
			if(v[b]) continue;
			have=true;
			for(int i=0; i<9; i++){
				SendA(!!((a-beeg)&(1<<i)));
			}
			break;
		}
		if(!have){
			mine={511,0};
			for(int i=0; i<9; i++){
				SendA(!!((mine.first)&(1<<i)));
			}
		}
	}
}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, vector<int> C) {
	n=N;
	got=0;
	for(int i=0; i<n; i++) v[i]=d[i]=0;
	for(int i=0; i<A; i++){
		adj[U[i]].push_back({V[i],C[i]});
		adj[V[i]].push_back({U[i],C[i]});
	}
	phase=0; beeg=0;
	pq.push({0,0});
	while(!pq.empty()){
		int a=pq.top().first,b=pq.top().second;
		mine={a-beeg,b};
		pq.pop();
		if(v[b]) continue;
		for(int i=0; i<9; i++){
			SendA(!!(a&(1<<i)));
		}
		break;
	}
}

void ReceiveA(bool x) {
	if(x) recv.push_back(1);
	else recv.push_back(0);
	if(phase==0&&(int)recv.size()==9){
		int opp=0;
		for(int i=0; i<9; i++){
			if(recv[i]) opp^=(1<<i);
		}
		recv.clear();
		if(mine.first<=opp){
			for(int i=0; i<11; i++){
				SendA(!!(mine.second&(1<<i)));
			}
			//cout << "me " << mine.second << ' ' << mine.first << '\n';
			//cout << opp << '\n';
			v[mine.second]=1;
			d[mine.second]=mine.first+beeg;
			got++; 
			beeg+=mine.first;
			if(got<n) loose(mine.second,beeg);
		}
		else{
			pq.push({mine.first+beeg,mine.second});
			mine.first=opp;
			phase=1;
			mine.second=0;
		}
	}
	else if(phase==1&&(int)recv.size()==11){
		mine.second=0;
		for(int i=0; i<11; i++){
			if(recv[i]) mine.second^=(1<<i);
		}
		recv.clear();
		//cout << "opp " << mine.second << ' ' << mine.first << '\n';
		v[mine.second]=1;
		d[mine.second]=mine.first+beeg;
		got++;
		beeg+=mine.first;
		if(got<n) loose(mine.second,beeg);
	}
}

std::vector<int> Answer() {
  std::vector<int> ans(n);
  for (int k = 0; k < n; ++k) {
    ans[k] = d[k];
  }
  return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
	int n;
	vector<pair<int,int> > adj[2005];
	int v[2005];
	int d[2005];
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
	vector<int> recv;
	int phase,beeg;
	pair<int,int> mine;
	int got;
	void loose(int x, int d){
		for(auto i:adj[x]){
			if(v[i.first]) continue;
			pq.push({d+i.second,i.first});
		}
		phase=0;
		bool have=false;
		while(!pq.empty()){
			int a=pq.top().first,b=pq.top().second;
			mine={a-beeg,b};
			pq.pop();
			if(v[b]) continue;
			have=true;
			break;
		}
		if(!have){
			mine={511,0};
		}
	}
}  // namespace

void InitB(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	n=N;
	got=0;
	for(int i=0; i<n; i++) v[i]=d[i]=0;
	for(int i=0; i<A; i++){
		adj[U[i]].push_back({V[i],C[i]});
		adj[V[i]].push_back({U[i],C[i]});
	}
	phase=0; beeg=0;
	pq.push({0,0});
	while(!pq.empty()){
		int a=pq.top().first,b=pq.top().second;
		mine={a-beeg,b};
		pq.pop();
		if(v[b]) continue;
		break;
	}
}

void ReceiveB(bool x) {
	if(x) recv.push_back(1);
	else recv.push_back(0);
	if(phase==0&&(int)recv.size()==9){
		int opp=0;
		for(int i=0; i<9; i++){
			if(recv[i]) opp^=(1<<i);
		}
		recv.clear();
		for(int i=0; i<9; i++){
			SendB(!!(mine.first&(1<<i)));
		}
		if(mine.first<opp){
			for(int i=0; i<11; i++){
				SendB(!!(mine.second&(1<<i)));
			}
			v[mine.second]=1;
			d[mine.second]=mine.first+beeg;
			got++; 
			beeg+=mine.first;
			if(got<n) loose(mine.second,beeg);
		}
		else{
			pq.push({mine.first+beeg,mine.second});
			mine.first=opp;
			phase=1;
			mine.second=0;
		}
	}
	else if(phase==1&&(int)recv.size()==11){
		mine.second=0;
		for(int i=0; i<11; i++){
			if(recv[i]) mine.second^=(1<<i);
		}
		recv.clear();
		v[mine.second]=1;
		d[mine.second]=mine.first+beeg;
		got++;
		beeg+=mine.first;
		if(got<n) loose(mine.second,beeg);
	}
}

• 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