# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
982555 | parlimoos | Two Transportations (JOI19_transportations) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "Baijan.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int nB , mB , dstB[2000];
vector<arr(2)> gB[2000];
set<arr(2)> qB;
int lstB = 0;
int rcvB[3] , xxB[2];
void sendInfB(int x , int len){
x = min(x , 501);
while(len == 11 and x > nB);
for(int bit = len - 1 ; bit >= 0 ; bit--) SendB(bool((x >> bit) & 1));
}
void addVtxB(int v , int x){
v = min(nB , v);
qB.erase({dstB[v] , v});
dstB[v] = x , lstB = x;
for(auto &e : gB[v]){
if(dstB[e[0]] > dstB[v] + e[1]){
qB.erase({dstB[e[0]] , e[0]});
dstB[e[0]] = dstB[v] + e[1];
qB.insert({dstB[e[0]] , e[0]});
}
}
auto itr = qB.bg();
rcvB[0] = 9 , rcvB[1] = 0 , rcvB[2] = 0;
xxB[0] = (*itr)[1] , xxB[1] = (*itr)[0] - lstB;
}
void gotLenB(int len){
if(xxB[1] <= len){
sendInfB(xxB[1] , 9);
sendInfB(xxB[1] , 11);
addVtxB(xxB[0] , xxB[1] + lstB);
}else{
int d = xxB[1];
rcvB[0] = 11 , rcvB[1] = 0 , rcvB[2] = 1 , xxB[1] = len;
sendInfB(d , 9);
}
}
void ReceiveB(bool x){
int vl = int(x);
rcvB[1] += (vl << (rcvB[0] - 1));
if(--rcvB[0] == 0){
if(rcvB[2] == 0) gotLenB(rcvB[1]);
else addVtxB(rcvB[1] , xxB[1] + lstB);
}
}
void InitB(int N , int B , vector<int> S , vector<int> T , vector<int> D){
nB = N , mB = B;
fill(&dstB[0] , &dstB[nB] , int(1e9));
for(int v = 0 ; v < nB ; v++) qB.insert({dstB[v] , v});
for(int i = 0 ; i < mB ; i++) gB[T[i]].pb({S[i] , D[i]}) , gB[S[i]].pb({T[i] , D[i]});
addVtxB(0 , 0);
}
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "Baijan.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
int nB , mB , dstB[2000];
vector<arr(2)> gB[2000];
set<arr(2)> qB;
int lstB = 0;
int rcvB[3] , xxB[2];
void sendInfB(int x , int len){
x = min(x , 501);
while(len == 11 and x > nB);
for(int bit = len - 1 ; bit >= 0 ; bit--) SendB(bool((x >> bit) & 1));
}
void addVtxB(int v , int x){
v = min(nB , v);
qB.erase({dstB[v] , v});
dstB[v] = x , lstB = x;
for(auto &e : gB[v]){
if(dstB[e[0]] > dstB[v] + e[1]){
qB.erase({dstB[e[0]] , e[0]});
dstB[e[0]] = dstB[v] + e[1];
qB.insert({dstB[e[0]] , e[0]});
}
}
auto itr = qB.bg();
rcvB[0] = 9 , rcvB[1] = 0 , rcvB[2] = 0;
xxB[0] = (*itr)[1] , xxB[1] = (*itr)[0] - lstB;
}
void gotLenB(int len){
if(xxB[1] <= len){
sendInfB(xxB[1] , 9);
sendInfB(xxB[1] , 11);
addVtxB(xxB[0] , xxB[1] + lstB);
}else{
int d = xxB[1];
rcvB[0] = 11 , rcvB[1] = 0 , rcvB[2] = 1 , xxB[1] = len;
sendInfB(d , 9);
}
}
void ReceiveB(bool x){
int vl = int(x);
rcvB[1] += (vl << (rcvB[0] - 1));
if(--rcvB[0] == 0){
if(rcvB[2] == 0) gotLenB(rcvB[1]);
else addVtxB(rcvB[1] , xxB[1] + lstB);
}
}
void InitB(int N , int B , vector<int> S , vector<int> T , vector<int> D){
nB = N , mB = B;
fill(&dstB[0] , &dstB[nB] , int(1e9));
for(int v = 0 ; v < nB ; v++) qB.insert({dstB[v] , v});
for(int i = 0 ; i < mB ; i++) gB[T[i]].pb({S[i] , D[i]}) , gB[S[i]].pb({T[i] , D[i]});
addVtxB(0 , 0);
}