Submission #708200

#	Time	Username	Problem	Language	Result	Execution time	Memory
708200		esomer	Two Transportations (JOI19_transportations)	C++17	0 / 100	3000 ms	656 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 node){
	int n = (int)dist.size();
	priority_queue<pair<int, int>> q; q.push({-dist[node], node});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != node) 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);
	int d = (*s.begin()).first;
	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((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((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> 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 node){
	int n = (int)dist.size();
	priority_queue<pair<int, int>> q; q.push({-dist[node], node});
	vector<bool> done(n, 0);
	while(!q.empty()){
		int x = q.top().second; q.pop();
		if(done[x]) continue;
		done[x] = 1;
		if(x != node) 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 InitB(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);
}

void ReceiveB(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;
		}
		return;
	}
	if(x) his += (1 << bit);
	int d = (*s.begin()).first; d -= mn;
	if((1 << bit) & d) {SendB(1); mine += (1 << bit);}
	else SendB(0);
	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) SendB(1);
				else SendB(0);
			}
		}else{
			receiving = 1;
		}
	}
}

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

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