Submission #395777

#	Time	Username	Problem	Language	Result	Execution time	Memory
395777		Osama_Alkhodairy	Two Transportations (JOI19_transportations)	C++17	100 / 100	2020 ms	67012 KiB

Azer

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

const int NA = 2001;
const int INFA = (int)1e9;

int nA;
vector <int> distA;
vector <pair <int, int> > vA[NA];
set <pair <int, int> > readyA;
int mx_distA = 0, cntA = 0, completeA = 0, waiting_forA;
vector <int> curA;

void addA(int node, int d){
    completeA++;
    mx_distA += d;
    distA[node] = mx_distA;
    for(auto &i : vA[node]){
        if(distA[node] + i.second < distA[i.first]){
            readyA.insert(make_pair(distA[node] + i.second, i.first));
        }
    }
}
pair <int, int> get_nextA(){
    while(readyA.size() && distA[readyA.begin()->second] != INFA){
        readyA.erase(readyA.begin());
    }
    if(readyA.size()){
        return make_pair(readyA.begin()->first - mx_distA, readyA.begin()->second);
    }
    return make_pair(511, 511);
}
void SendA(){
    if(completeA == nA) return;
    waiting_forA = 9;
    pair <int, int> f = get_nextA();
    for(int i = 8 ; i >= 0 ; i--){
        SendA((f.first >> i) & 1);
    }
}
void InitA(int N, int A, vector <int> U, vector <int> V, vector <int> C){
    nA = N;
    for(int i = 0 ; i < A ; i++){
        vA[U[i]].push_back(make_pair(V[i], C[i]));
        vA[V[i]].push_back(make_pair(U[i], C[i]));
    }
    distA.resize(N, INFA);
    distA[0] = 0;
    addA(0, 0);
    SendA();
}
void ReceiveA(bool x){
    if(curA.size() == 0) curA.push_back(0);
    curA.back() = curA.back() * 2 + x;
    cntA++;
    if(cntA == waiting_forA){
        if(waiting_forA == 9){
            auto g = get_nextA();
            if(g.first <= curA.back()){
                for(int i = 10 ; i >= 0 ; i--){
                    SendA((g.second >> i) & 1);
                }
                curA.clear();
                cntA = 0;
                addA(g.second, g.first);
                SendA();
            }
            else{
                curA.push_back(0);
                cntA = 0;
                waiting_forA = 11;
            }
        }
        else{
            assert(curA.size() == 2);
            addA(curA[1], curA[0]);
            SendA();
            curA.clear();
            cntA = 0;
        }
    }
}
vector <int> Answer(){
    return distA;
}

Baijan

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

const int NB = 2001;
const int INFB = (int)1e9;

int nB;
vector <int> distB;
vector <pair <int, int> > vB[NB];
set <pair <int, int> > readyB;
int mx_distB = 0, cntB = 0, waiting_forB;
vector <int> curB;

void addB(int node, int d){
    mx_distB += d;
    distB[node] = mx_distB;
    for(auto &i : vB[node]){
        if(distB[node] + i.second < distB[i.first]){
            readyB.insert(make_pair(distB[node] + i.second, i.first));
        }
    }
}
pair <int, int> get_nextB(){
    while(readyB.size() && distB[readyB.begin()->second] != INFB){
        readyB.erase(readyB.begin());
    }
    if(readyB.size()){
        return make_pair(readyB.begin()->first - mx_distB, readyB.begin()->second);
    }
    return make_pair(511, 511);
}
void InitB(int N, int B, vector <int> S, vector <int> T, vector <int> D){
    nB = N;
    for(int i = 0 ; i < B ; i++){
        vB[S[i]].push_back(make_pair(T[i], D[i]));
        vB[T[i]].push_back(make_pair(S[i], D[i]));
    }
    distB.resize(N, INFB);
    distB[0] = 0;
    addB(0, 0);
    waiting_forB = 9;
}
void ReceiveB(bool y){
    if(curB.size() == 0) curB.push_back(0);
    curB.back() = 2 * curB.back() + y;
    cntB++;
    if(cntB == waiting_forB){
        if(waiting_forB == 9){
            auto g = get_nextB();
            if(g.first < curB.back()){
                for(int i = 8 ; i >= 0 ; i--){
                    SendB((g.first >> i) & 1);
                }
                for(int i = 10 ; i >= 0 ; i--){
                    SendB((g.second >> i) & 1);
                }
                addB(g.second, g.first);
                curB.clear();
                cntB = 0;
                waiting_forB = 9;
            }
            else{
                for(int i = 8 ; i >= 0 ; i--){
                    SendB(1);
                }
                waiting_forB = 11;
                curB.push_back(0);
                cntB = 0;
            }
        }
        else{
            assert(curB.size() == 2);
            addB(curB[1], curB[0]);
            curB.clear();
            cntB = 0;
            waiting_forB = 9;
        }
    }
}

• 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