oj.uz

Submission #985981

# Submission time Handle Problem Language Result Execution time Memory
985981 2024-05-19T13:43:00 Z SzymonKrzywda Two Transportations (JOI19_transportations) C++17
62 / 100
 650 ms 74808 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,507)==507 && info[0]==507) return;
            send(min(akt_top.first-suma,507),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({MAXN,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="";
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,507)==507 && info[0]==507) 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,507),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] > suma+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,507),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,507),9);
    //cout << "ELO" <<endl;
 
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 248 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 Correct 6 ms 24216 KB Output is correct
2 Runtime error 168 ms 12108 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 24308 KB Output is correct
2 Correct 221 ms 24276 KB Output is correct
3 Correct 309 ms 36780 KB Output is correct
4 Correct 180 ms 24336 KB Output is correct
5 Correct 217 ms 33444 KB Output is correct
6 Correct 146 ms 24316 KB Output is correct
7 Correct 167 ms 24352 KB Output is correct
8 Correct 140 ms 24348 KB Output is correct
9 Correct 337 ms 44360 KB Output is correct
10 Correct 326 ms 45768 KB Output is correct
11 Correct 458 ms 63644 KB Output is correct
12 Correct 430 ms 61500 KB Output is correct
13 Correct 162 ms 24216 KB Output is correct
14 Correct 8 ms 24216 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 24308 KB Output is correct
2 Correct 221 ms 24276 KB Output is correct
3 Correct 309 ms 36780 KB Output is correct
4 Correct 180 ms 24336 KB Output is correct
5 Correct 217 ms 33444 KB Output is correct
6 Correct 146 ms 24316 KB Output is correct
7 Correct 167 ms 24352 KB Output is correct
8 Correct 140 ms 24348 KB Output is correct
9 Correct 337 ms 44360 KB Output is correct
10 Correct 326 ms 45768 KB Output is correct
11 Correct 458 ms 63644 KB Output is correct
12 Correct 430 ms 61500 KB Output is correct
13 Correct 162 ms 24216 KB Output is correct
14 Correct 8 ms 24216 KB Output is correct
15 Correct 164 ms 24216 KB Output is correct
16 Correct 205 ms 24256 KB Output is correct
17 Correct 187 ms 24216 KB Output is correct
18 Correct 257 ms 34136 KB Output is correct
19 Correct 196 ms 24356 KB Output is correct
20 Correct 286 ms 34132 KB Output is correct
21 Correct 185 ms 24216 KB Output is correct
22 Correct 236 ms 24364 KB Output is correct
23 Correct 365 ms 48748 KB Output is correct
24 Correct 352 ms 47876 KB Output is correct
25 Correct 603 ms 70488 KB Output is correct
26 Correct 417 ms 66416 KB Output is correct
27 Correct 212 ms 24564 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 24308 KB Output is correct
2 Correct 221 ms 24276 KB Output is correct
3 Correct 309 ms 36780 KB Output is correct
4 Correct 180 ms 24336 KB Output is correct
5 Correct 217 ms 33444 KB Output is correct
6 Correct 146 ms 24316 KB Output is correct
7 Correct 167 ms 24352 KB Output is correct
8 Correct 140 ms 24348 KB Output is correct
9 Correct 337 ms 44360 KB Output is correct
10 Correct 326 ms 45768 KB Output is correct
11 Correct 458 ms 63644 KB Output is correct
12 Correct 430 ms 61500 KB Output is correct
13 Correct 162 ms 24216 KB Output is correct
14 Correct 8 ms 24216 KB Output is correct
15 Correct 164 ms 24216 KB Output is correct
16 Correct 205 ms 24256 KB Output is correct
17 Correct 187 ms 24216 KB Output is correct
18 Correct 257 ms 34136 KB Output is correct
19 Correct 196 ms 24356 KB Output is correct
20 Correct 286 ms 34132 KB Output is correct
21 Correct 185 ms 24216 KB Output is correct
22 Correct 236 ms 24364 KB Output is correct
23 Correct 365 ms 48748 KB Output is correct
24 Correct 352 ms 47876 KB Output is correct
25 Correct 603 ms 70488 KB Output is correct
26 Correct 417 ms 66416 KB Output is correct
27 Correct 212 ms 24564 KB Output is correct
28 Correct 264 ms 24728 KB Output is correct
29 Correct 264 ms 24292 KB Output is correct
30 Correct 464 ms 47572 KB Output is correct
31 Correct 275 ms 24284 KB Output is correct
32 Correct 362 ms 44996 KB Output is correct
33 Correct 292 ms 24356 KB Output is correct
34 Correct 280 ms 24388 KB Output is correct
35 Correct 264 ms 24388 KB Output is correct
36 Correct 396 ms 50276 KB Output is correct
37 Correct 427 ms 51260 KB Output is correct
38 Correct 650 ms 74808 KB Output is correct
39 Correct 565 ms 72792 KB Output is correct
40 Correct 220 ms 24876 KB Output is correct

Subtask #7
0 / 16.0

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