Submission #1105236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105236		jamesbamber	Two Transportations (JOI19_transportations)	C++17	100 / 100	729 ms	53732 KiB

Azer

#include "Azer.h"

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

namespace {

constexpr int INF = 1e8;

vector<vector<pair<int,int>>> ad;

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
vector<int> vis;
vector<int> dist;

void add_pq(int v, int d){
    //cerr << "Azer: " << v << " " << d << endl;
    for(auto [u, w]: ad[v]){
        if(d + w < dist[u]){
            pq.emplace(d+w, u);
        }
    }
}

int N;

bool receive_type; // 0 for distance, 1 for node index
int counter, count_vis;
int received_node, received_dist;
int curr_node, curr_dist;
int last_dist;

void find_next(){
    last_dist = min(curr_dist, received_dist);

    while(pq.size() and vis[pq.top().second]) pq.pop();

    if(pq.size()) curr_dist = pq.top().first, curr_node = pq.top().second;
    else curr_dist = last_dist+501, curr_node = 0;

    received_node = 0;
    received_dist = last_dist;

    for(int i=0; i<9; i++) SendA((1 << i) & (curr_dist - last_dist));
}

void visit(int v, int d){
    dist[v] = d; vis[v] = 1; count_vis++;
    add_pq(v, d);
    if(count_vis < N) find_next();
}

}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
    ::N = N;

    ad.resize(N), vis.resize(N), dist.resize(N, INF);
    for(int i=0; i<A; i++){
        ad[U[i]].push_back({V[i], C[i]});
        ad[V[i]].push_back({U[i], C[i]});
    }
    
    dist[0] = 0;
    pq.emplace(0, 0);
    find_next();
}

void ReceiveA(bool x) {

    if(receive_type == 0){
        received_dist += int(x) << counter;
        counter++;
        if(counter == 9){
            if(curr_dist <= received_dist){ 
                for(int i=0; i<11; i++) SendA((1 << i) & curr_node);

                pq.pop();
                visit(curr_node, curr_dist);

            }
            else{
                receive_type = 1;
            }
            counter = 0;
        }
    }
    else{
        received_node += int(x) << counter;
        counter++;
        if(counter == 11){
            visit(received_node, received_dist);

            receive_type = 0;
            counter = 0;
        }
    }
}

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

Baijan

#include "Baijan.h"

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

namespace {

constexpr int INF = 1e8;

vector<vector<pair<int,int>>> ad;

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
vector<int> vis;
vector<int> dist;

void add_pq(int v, int d){
    //cerr << "Baijan: " << v << " " << d << endl;
    for(auto [u, w]: ad[v]){
        if(d + w < dist[u]){
            pq.emplace(d+w, u);
        }
    }
}

int N;

bool receive_type; // 0 for distance, 1 for node index
int counter, count_vis;
int received_node, received_dist;
int curr_node, curr_dist;
int last_dist;

void find_next(){
    last_dist = min(curr_dist, received_dist);

    while(pq.size() and vis[pq.top().second]) pq.pop();

    if(pq.size()) curr_dist = pq.top().first, curr_node = pq.top().second;
    else curr_dist = last_dist+501, curr_node = 0;

    received_node = 0;
    received_dist = last_dist;

    for(int i=0; i<9; i++) SendB((1 << i) & (curr_dist - last_dist));
}

void visit(int v, int d){
    dist[v] = d; vis[v] = 1; count_vis++;
    add_pq(v, d);
    if(count_vis < N) find_next();
}

}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
    ::N = N;

    ad.resize(N), vis.resize(N), dist.resize(N, INF);
    for(int i=0; i<B; i++){
        ad[S[i]].push_back({T[i], D[i]});
        ad[T[i]].push_back({S[i], D[i]});
    }
    
    dist[0] = 0;
    pq.emplace(0, 0);
    find_next();
}

void ReceiveB(bool y) {
    if(receive_type == 0){
        received_dist += int(y) << counter;
        counter++;
        if(counter == 9){
            if(curr_dist < received_dist){ 
                for(int i=0; i<11; i++) SendB((1 << i) & curr_node);

                pq.pop();
                visit(curr_node, curr_dist);
            }
            else{
                receive_type = 1;
            }
            counter = 0;
        }
    }
    else{
        received_node += int(y) << counter;
        counter++;
        if(counter == 11){
            visit(received_node, received_dist);

            receive_type = 0;
            counter = 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