Submission #985922

#	Time	Username	Problem	Language	Result	Execution time	Memory
985922		SzymonKrzywda	Two Transportations (JOI19_transportations)	C++17	0 / 100	3000 ms	36652 KiB

Azer

#include <bits/stdc++.h>
#include "Azer.h"

using namespace std;

namespace{
pair <int,int> akt_top;
int akt = 0;
int akt_2 = 0;
int akt_bits = 9;
string akt_str = "";
vector<int> answer={0};
int info[2];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
vector<vector<pair<int,int>>> graf(500000);

string decToBinary(int n,int bits)
{
    string ans = "";
    for (int i = bits; i >= 0; i--) {
        int k = n >> i;
        if (k & 1)
            ans += "1";
        else
            ans += "0";
    }
    return ans;
}

int binaryToDecimal(string str)
{
    int dec_num = 0;
    int power = 0 ;
    int n = str.length() ; 
   
      for(int i = n-1 ; i>=0 ; i--){
      if(str[i] == '1'){
        dec_num += (1<<power) ;
      }
      power++ ; 
    }
   
    return dec_num;
}

void send(int a,int bits){
    string bin = decToBinary(a,bits);
    for (int i=0; i<bits+1; i++){
        SendA(bin[i]);
    }
}
}

void ReceiveA(bool x){
    if (x == 0) akt_str += "0";
    else akt_str += "1";
    
    if (akt_2==akt_bits){
        int liczba = binaryToDecimal(akt_str);

        if (akt==0){ // wartosc
            info[0] = liczba;
            while (answer[pq.top().second] <= pq.top().first) pq.pop();
            if (pq.empty()) pq.push({512,2024});
            akt_top = pq.top();
            if (akt_top.first==512 && info[0]==512) return;
            send(akt_top.first,9);
            if (akt_top.first < info[0]){
                send(akt_top.second,11);
                pq.pop();
                answer[akt_top.second] = akt_top.first;
                //// DIJKSTRA
                for (auto [a,val] : graf[akt_top.second]){
                    if (answer[a] > akt_top.first+val){
                        pq.push({akt_top.first+val,a});
                    }
                }
                akt_bits = 9;
            }
            else{
                akt = 1;
                akt_bits = 11;
            }
        }
        else if(akt==1){ // Wierzcholek
            info[1] = liczba;
            answer[info[1]] = info[0]; 
            for (auto [a,val] : graf[info[1]]){
                if (answer[a] > info[0]+val){
                    pq.push({info[0]+val,a});
                }
            }
            akt = 0;
            akt_bits = 9;
        }
        akt_2 = 0;
        akt_str = "";
    }
    else akt_2 += 1;
}



void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C){
    for (int i=1; i<N; i++){
        answer.push_back(9999999);
    }
    for (int i=0; i<A; i++){
        graf[U[i]].push_back({V[i],C[i]});
        graf[V[i]].push_back({U[i],C[i]});
    }
    for (auto [a,val] : graf[0]){
        pq.push({val,a});
    }
    pq.push({512,2024});
    
}

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

Baijan

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

namespace{
pair <int,int> akt_top;
int akt = 0,akt_2=0,akt_bits=9;
int info[2];
string akt_str="";
int akt_stan = 0;// 0 - wyslij val, 1 - otrzymaj val, 3-otrzymaj v
vector<int> answer={0};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
vector<vector<pair<int,int>>> graf(500000);

string decToBinary(int n,int bits)
{
    string ans = "";
    for (int i = bits; i >= 0; i--) {
        int k = n >> i;
        if (k & 1)
            ans += "1";
        else
            ans += "0";
    }
    return ans;
}

int binaryToDecimal(string str)
{
    int dec_num = 0;
    int power = 0 ;
    int n = str.length() ; 
   
      for(int i = n-1 ; i>=0 ; i--){
      if(str[i] == '1'){
        dec_num += (1<<power) ;
      }
      power++ ; 
    }
   
    return dec_num;
}

void send(int a,int bits){
    int c=a;
    string bin = decToBinary(a,bits);
    for (int i=0; i<bits+1; i++){
        SendB(bin[i]-'0');
    }
}
}
void ReceiveB(bool y){
    if (y == 0) akt_str += "0";
    else akt_str += "1";
    
    if (akt_2==akt_bits){
        int liczba = binaryToDecimal(akt_str);

        if (akt==0){ // wartosc
            info[0] = liczba;
            while (answer[pq.top().second] <= pq.top().first) pq.pop();
            if (pq.empty()) pq.push({512,2024});
            akt_top = pq.top();
            if (akt_top.first==512 && info[0]==512) return;
            //send(akt_top.first,9);
            if (akt_top.first <= info[0]){
                send(akt_top.second,11);
                pq.pop();
                answer[akt_top.second] = akt_top.first;
                //// DIJKSTRA
                for (auto [a,val] : graf[akt_top.second]){
                    if (answer[a] > akt_top.first+val){
                        pq.push({akt_top.first+val,a});
                    }
                }
                akt_bits = 9;
                while (answer[pq.top().second] <= pq.top().first) pq.pop();
                if (pq.empty()) pq.push({512,2024});
                send(pq.top().first,9);
            }
            else{
                akt = 1;
                akt_bits = 11;
            }
        }
        else if(akt==1){ // Wierzcholek
            info[1] = liczba;
            answer[info[1]] = info[0]; 
            for (auto [a,val] : graf[info[1]]){
                if (answer[a] > info[0]+val){
                    pq.push({info[0]+val,a});
                }
            }
            akt = 0;
            akt_bits = 9;
            while (answer[pq.top().second] <= pq.top().first) pq.pop();
            if (pq.empty()) pq.push({512,2024});
            send(pq.top().first,9);
        }
        akt_2 = 0;
        akt_str = "";
    }
    else akt_2 += 1;
}

void SendB(bool x);

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D){
    for (int i=1; i<N; i++){
        answer.push_back(9999999);
    }
    for (int i=0; i<B; i++){
        graf[S[i]].push_back({T[i],D[i]});
        graf[T[i]].push_back({S[i],D[i]});
    }
    for (auto [a,val] : graf[0]){
        pq.push({val,a});
    }
    pq.push({512,2024});
    send(pq.top().first,9);

    
}

Compilation message (stderr)

Baijan.cpp: In function 'void {anonymous}::send(int, int)':
Baijan.cpp:45:9: warning: unused variable 'c' [-Wunused-variable]
   45 |     int c=a;
      |         ^
Baijan.cpp: At global scope:
Baijan.cpp:10:5: warning: '{anonymous}::akt_stan' defined but not used [-Wunused-variable]
   10 | int akt_stan = 0;// 0 - wyslij val, 1 - otrzymaj val, 3-otrzymaj v
      |     ^~~~~~~~

• 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