oj.uz

Submission #985966

# Submission time Handle Problem Language Result Execution time Memory
985966 2024-05-19T13:08:16 Z SzymonKrzywda Two Transportations (JOI19_transportations) C++17
0 / 100
 6 ms 12108 KB 
#include <bits/stdc++.h>
#include "Azer.h"
 
using namespace std;
 
namespace{
const int MAXN = 99999999;
int suma = 0;
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);
    //cout << "WYSYLA A: " << a << " z tyloma bitami: " << bits << " " << bin <<  endl;
    for (int i=0; i<bits+1; i++){
        SendA(bin[i]-'0');
    }
}
}
 
void ReceiveA(bool x){
    if (x == 0) akt_str += "0";
    else akt_str += "1";
 
    if (akt_2==akt_bits){
        int liczba = binaryToDecimal(akt_str);
        //cout << "otrzymal A: " << liczba << " akt bity: " << akt_bits << " str "<< akt_str <<endl;
        if (akt==0){ // wartosc
            info[0] = liczba;
            while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) {
                    pq.pop();
            }
 
            if (pq.empty()) pq.push({MAXN,2024});
            akt_top = pq.top();
            if (min(akt_top.first-suma,512)==512 && info[0]==512) return;
            send(min(akt_top.first-suma,512),9);
            if (akt_top.first-suma < info[0]){
                suma = akt_top.first;
                send(akt_top.second,11);
                pq.pop();
                answer[akt_top.second] = akt_top.first;
                //cout << "A WYBRANY: " << akt_top.first<<endl;
                //// DIJKSTRA
                for (auto [a,val] : graf[akt_top.second]){
                    if (answer[a] > akt_top.first+val){
                        pq.push({akt_top.first+val,a});
                    }
                }
                //for (auto i : answer) cout << i << " ";
                //    cout << endl;
                akt_bits = 9;
            }
            else{
                akt = 1;
                akt_bits = 11;
            }
        }
        else if(akt==1){ // Wierzcholek
            info[1] = liczba;
            suma += info[0];
            answer[info[1]] = suma;
            //cout << "A WYBRANY: " << info[0]<<endl;
            for (auto [a,val] : graf[info[1]]){
                if (answer[a] > suma+val){
                    pq.push({suma+val,a});
                }
            }
            //for (auto i : answer) cout << i << " ";
            //cout << endl;
            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;
}
#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;
 
namespace{
const int MAXN = 99999999;
int suma = 0;
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){
 
    string bin = decToBinary(a,bits);
        cout << "WYSYLA B: " << a << " z tyloma bitami: " << bits << " " << bin << endl;
    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";
    //cout << akt_bits << " " << akt_2 <<endl;
    if (akt_2==akt_bits){
        int liczba = binaryToDecimal(akt_str);
        //cout << "otrzymal B: " << liczba << " akt bity: " << akt_bits << " str "<< akt_str <<endl;
        if (akt==0){ // wartosc
            info[0] = liczba;
            //cout << "TEST" << endl;
            while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) pq.pop();
            if (pq.empty()) pq.push({MAXN,2024});
            akt_top = pq.top();
            if (min(akt_top.first-suma,512)==512 && info[0]==512) return;
            //send(akt_top.first,9);
            if (akt_top.first-suma <= info[0]){
                suma = akt_top.first;
                send(akt_top.second,11);
                pq.pop();
                answer[akt_top.second] = akt_top.first;
                //cout << "B WYBRANY: " << akt_top.first << " " << akt_top.second <<endl;
                //// DIJKSTRA
                //cout << " TETS";
                for (auto [a,val] : graf[akt_top.second]){
                    //cout << answer[a] << " " << a << " " << akt_top.first << endl;
                    if (answer[a] > akt_top.first+val){
                        pq.push({akt_top.first+val,a});
                    }
                }
 
                akt_bits = 9;
                //cout << " TETS2";
                //cout << pq.top().first << endl;
                while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) {
                        //cout << pq.top().first << " " << pq.top().second << endl;
                        pq.pop();
                }
                //cout << "DWD";
                            //for (auto i : answer) cout << i << " ";
            //cout << endl;
                if (pq.empty()) pq.push({MAXN,2024});
            //cout << "DW";
                send(min(pq.top().first-suma,512),9);
            //cout << " TETS";
            }
            else{
                akt = 1;
                akt_bits = 11;
            }
        }
        else if(akt==1){ // Wierzcholek
            info[1] = liczba;
            suma += info[0];
            answer[info[1]] = suma;
            //cout << "B WYBRANY: " << info[0]<<endl;
            for (auto [a,val] : graf[info[1]]){
                //cout << answer[a] << " " << a << " " << info[0] << endl;
                if (answer[a] > info[0]+val){
                    pq.push({suma+val,a});
                }
            }
            //for (auto i : answer) cout << i << " ";
            //cout << endl;
            akt = 0;
            akt_bits = 9;
            while (pq.top().first != MAXN && answer[pq.top().second] <= pq.top().first) pq.pop();
            if (pq.empty()) pq.push({MAXN,2024});
            send(min(pq.top().first-suma,512),9);
        }
        akt_2 = 0;
        akt_str = "";
        //cout << "TEST#";
    }
    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({MAXN,2024});
    send(min(pq.top().first-suma,512),9);
    //cout << "ELO" <<endl;
 
}

Compilation message

Baijan.cpp:12:5: warning: '{anonymous}::akt_stan' defined but not used [-Wunused-variable]
   12 | int akt_stan = 0;// 0 - wyslij val, 1 - otrzymaj val, 3-otrzymaj v
      |     ^~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 12108 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 12108 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 12108 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 12096 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 12096 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 12096 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 12108 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -