Submission #708221

#	Time	Username	Problem	Language	Result	Execution time	Memory
708221		esomer	Two Transportations (JOI19_transportations)	C++17	100 / 100	835 ms	48824 KiB

Azer

#include<bits/stdc++.h>
#include "Azer.h"
 
using namespace std;
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

vector<int> dist;
set<pair<int, int>> s;
vector<vector<pair<int, int>>> adj;
int mn = 0, bit = 8, mine = 0, his = 0, bit2 = 10, nd = 0;
bool receiving = 0;

void Dijkstra(int nod){
	int n = (int)dist.size();
	priority_queue<pair<int, int>> q; q.push({-dist[nod], nod});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != nod) s.insert({dist[x], x});
		for(auto p : adj[x]){
			int node = p.first;
			if(dist[node] > dist[x] + p.second){
				s.erase({dist[node], node});
				dist[node] = dist[x] + p.second;
				q.push({-dist[node], node});
			}
		}
	}
}

void InitA(int n, int m, vector<int> U, vector<int> V, vector<int> C){
	dist.assign(n, 1e9); dist[0] = 0;
	adj.assign(n, {});
	for(int i = 0; i < m; i++){
		adj[U[i]].push_back({V[i], C[i]});
		adj[V[i]].push_back({U[i], C[i]});
	}
	Dijkstra(0);
	if(n == 1) return;
	for(int i = 1; i < n; i++){
		if(dist[i] == 1e9) s.insert({1e9, i});
	}
	int d = (*s.begin()).first;
	if(d > 500) d = 511;
	if((1 << bit) & d) {SendA(1); mine += (1 << bit);}
	else SendA(0);
}

void start(){
	if((int)s.size() == 0) return;
	bit = 8; mine = 0; his = 0;
	int d = (*s.begin()).first; d -= mn;
	if(d > 500) d = 511;
	if((1 << bit) & d) {SendA(1); mine += (1 << bit);}
	else SendA(0);
}

void ReceiveA(bool x){
	if(receiving){
		if(x) nd += (1 << bit2);
		bit2--;
		if(bit2 == -1){
			s.erase({dist[nd], nd});
			dist[nd] = mn;
			Dijkstra(nd);
			receiving = 0;
			nd = 0;
			bit2 = 10;
			start();
		}
		return;
	}
	if(x) his += (1 << bit);
	bit--;
	if(bit == -1){
		//Si él gana, simplemente receiving = 1, y return;
		//Si gano yo, le paso la info del nodo y luego hago start().
		mn += min(mine, his);
		if(mine <= his){//Para Baijan esto es < his.
			int node = (*s.begin()).second; s.erase(s.begin());
			for(int i = 10; i >= 0; i--){
				if((1 << i) & node) SendA(1);
				else SendA(0);
			}
			start();
		}else{
			receiving = 1;
		}
	}else{
		int d = (*s.begin()).first; d -= mn;
		if(d > 500) d = 511;
		if((1 << bit) & d) {SendA(1); mine += (1 << bit);}
		else SendA(0);
	}
}

vector<int> Answer(){
	return dist;
}

Baijan

#include<bits/stdc++.h>
#include "Baijan.h"
 
using namespace std;
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

vector<int> distB;
set<pair<int, int>> sB;
vector<vector<pair<int, int>>> adjB;
int mnB = 0, bitB = 8, mineB = 0, hisB = 0, bit2B = 10, ndB = 0;
bool receivingB = 0;

void DijkstraB(int nod){
	int n = (int)distB.size();
	priority_queue<pair<int, int>> q; q.push({-distB[nod], nod});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != nod) sB.insert({distB[x], x});
		for(auto p : adjB[x]){
			int node = p.first;
			if(distB[node] > distB[x] + p.second){
				sB.erase({distB[node], node});
				distB[node] = distB[x] + p.second;
				q.push({-distB[node], node});
			}
		}
	}
}

void InitB(int n, int m, vector<int> U, vector<int> V, vector<int> C){
	distB.assign(n, 1e9); distB[0] = 0;
	adjB.assign(n, {});
	for(int i = 0; i < m; i++){
		adjB[U[i]].push_back({V[i], C[i]});
		adjB[V[i]].push_back({U[i], C[i]});
	}
	DijkstraB(0);
	if(n == 1) return;
	for(int i = 1; i < n; i++){
		if(distB[i] == 1e9) sB.insert({1e9, i});
	}
}

void ReceiveB(bool x){
	if(receivingB){
		if(x) ndB += (1 << bit2B);
		bit2B--;
		if(bit2B == -1){
			sB.erase({distB[ndB], ndB});
			distB[ndB] = mnB;
			DijkstraB(ndB);
			receivingB = 0;
			ndB = 0;
			bit2B = 10;
			bitB = 8; mineB = 0; hisB = 0;
		}
		return;
	}
	if(x) hisB += (1 << bitB);
	int d = (*sB.begin()).first; d -= mnB;
	if(d > 500) d = 511;
	if((1 << bitB) & d) {SendB(1); mineB += (1 << bitB);}
	else SendB(0);
	bitB--;
	if(bitB == -1){
		//Si él gana, simplemente receiving = 1, y return;
		//Si gano yo, le paso la info del nodo y luego hago start().
		//~ cout << "B mine " << mineB << " his " << hisB << endl;
		mnB += min(mineB, hisB);
		if(mineB < hisB){//Para Baijan esto es < his.
			int node = (*sB.begin()).second; sB.erase(sB.begin());
			for(int i = 10; i >= 0; i--){
				if((1 << i) & node) SendB(1);
				else SendB(0);
			}
			bitB = 8; mineB = 0; hisB = 0;
		}else{
			receivingB = 1;
		}
	}
}

• 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