oj.uz

Submission #985973

# Submission time Handle Problem Language Result Execution time Memory
985973 2024-05-19T13:17:39 Z SzymonKrzywda Two Transportations (JOI19_transportations) C++17
62 / 100
 729 ms 75564 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({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,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] > 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,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;
 
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 234 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 9 ms 24216 KB Output is correct
2 Runtime error 203 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 156 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 147 ms 24308 KB Output is correct
2 Correct 151 ms 24280 KB Output is correct
3 Correct 277 ms 36816 KB Output is correct
4 Correct 173 ms 24408 KB Output is correct
5 Correct 236 ms 33640 KB Output is correct
6 Correct 185 ms 24216 KB Output is correct
7 Correct 151 ms 24216 KB Output is correct
8 Correct 162 ms 24348 KB Output is correct
9 Correct 336 ms 43816 KB Output is correct
10 Correct 325 ms 44436 KB Output is correct
11 Correct 521 ms 64660 KB Output is correct
12 Correct 433 ms 62236 KB Output is correct
13 Correct 194 ms 24216 KB Output is correct
14 Correct 9 ms 24216 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 24308 KB Output is correct
2 Correct 151 ms 24280 KB Output is correct
3 Correct 277 ms 36816 KB Output is correct
4 Correct 173 ms 24408 KB Output is correct
5 Correct 236 ms 33640 KB Output is correct
6 Correct 185 ms 24216 KB Output is correct
7 Correct 151 ms 24216 KB Output is correct
8 Correct 162 ms 24348 KB Output is correct
9 Correct 336 ms 43816 KB Output is correct
10 Correct 325 ms 44436 KB Output is correct
11 Correct 521 ms 64660 KB Output is correct
12 Correct 433 ms 62236 KB Output is correct
13 Correct 194 ms 24216 KB Output is correct
14 Correct 9 ms 24216 KB Output is correct
15 Correct 241 ms 24216 KB Output is correct
16 Correct 199 ms 24340 KB Output is correct
17 Correct 168 ms 24344 KB Output is correct
18 Correct 268 ms 33676 KB Output is correct
19 Correct 186 ms 24216 KB Output is correct
20 Correct 254 ms 34124 KB Output is correct
21 Correct 229 ms 24216 KB Output is correct
22 Correct 205 ms 24472 KB Output is correct
23 Correct 348 ms 48776 KB Output is correct
24 Correct 442 ms 47984 KB Output is correct
25 Correct 554 ms 70248 KB Output is correct
26 Correct 453 ms 66952 KB Output is correct
27 Correct 265 ms 24564 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 24308 KB Output is correct
2 Correct 151 ms 24280 KB Output is correct
3 Correct 277 ms 36816 KB Output is correct
4 Correct 173 ms 24408 KB Output is correct
5 Correct 236 ms 33640 KB Output is correct
6 Correct 185 ms 24216 KB Output is correct
7 Correct 151 ms 24216 KB Output is correct
8 Correct 162 ms 24348 KB Output is correct
9 Correct 336 ms 43816 KB Output is correct
10 Correct 325 ms 44436 KB Output is correct
11 Correct 521 ms 64660 KB Output is correct
12 Correct 433 ms 62236 KB Output is correct
13 Correct 194 ms 24216 KB Output is correct
14 Correct 9 ms 24216 KB Output is correct
15 Correct 241 ms 24216 KB Output is correct
16 Correct 199 ms 24340 KB Output is correct
17 Correct 168 ms 24344 KB Output is correct
18 Correct 268 ms 33676 KB Output is correct
19 Correct 186 ms 24216 KB Output is correct
20 Correct 254 ms 34124 KB Output is correct
21 Correct 229 ms 24216 KB Output is correct
22 Correct 205 ms 24472 KB Output is correct
23 Correct 348 ms 48776 KB Output is correct
24 Correct 442 ms 47984 KB Output is correct
25 Correct 554 ms 70248 KB Output is correct
26 Correct 453 ms 66952 KB Output is correct
27 Correct 265 ms 24564 KB Output is correct
28 Correct 253 ms 24332 KB Output is correct
29 Correct 220 ms 24284 KB Output is correct
30 Correct 509 ms 47548 KB Output is correct
31 Correct 264 ms 24288 KB Output is correct
32 Correct 459 ms 44712 KB Output is correct
33 Correct 272 ms 24364 KB Output is correct
34 Correct 233 ms 24388 KB Output is correct
35 Correct 236 ms 24392 KB Output is correct
36 Correct 417 ms 49688 KB Output is correct
37 Correct 548 ms 50420 KB Output is correct
38 Correct 729 ms 75564 KB Output is correct
39 Correct 568 ms 72848 KB Output is correct
40 Correct 206 ms 24632 KB Output is correct

Subtask #7
0 / 16.0

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