oj.uz

Submission #986036

# Submission time Handle Problem Language Result Execution time Memory
986036 2024-05-19T16:34:39 Z SzymonKrzywda Two Transportations (JOI19_transportations) C++17
100 / 100
 720 ms 76352 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){
    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-1){
        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{
int n;
int liczba_odw = 0;
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){
    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-1){
        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]){
                liczba_odw ++;
                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";
                if (liczba_odw==n) return;
                send(min(pq.top().first-suma,507),9);
            //cout << " TETS";
            }
            else{
                akt = 1;
                akt_bits = 11;
            }
        }
        else if(akt==1){ // Wierzcholek
            liczba_odw ++;
            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});
            if (liczba_odw==n) return;
            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){
    n = N;
    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});
    liczba_odw ++;
    send(min(pq.top().first,507),9);
    //cout << "ELO" <<endl;

}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 24544 KB Output is correct
2 Correct 8 ms 24216 KB Output is correct
3 Correct 296 ms 24288 KB Output is correct
4 Correct 451 ms 33768 KB Output is correct
5 Correct 25 ms 24564 KB Output is correct
6 Correct 387 ms 26796 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24216 KB Output is correct
2 Correct 368 ms 24364 KB Output is correct
3 Correct 372 ms 24428 KB Output is correct
4 Correct 481 ms 51448 KB Output is correct
5 Correct 499 ms 50664 KB Output is correct
6 Correct 57 ms 24336 KB Output is correct
7 Correct 532 ms 49140 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 24348 KB Output is correct
2 Correct 7 ms 24216 KB Output is correct
3 Correct 395 ms 24288 KB Output is correct
4 Correct 332 ms 24360 KB Output is correct
5 Correct 343 ms 24364 KB Output is correct
6 Correct 335 ms 24352 KB Output is correct
7 Correct 392 ms 24360 KB Output is correct
8 Correct 351 ms 24292 KB Output is correct
9 Correct 343 ms 24288 KB Output is correct
10 Correct 393 ms 24500 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 24480 KB Output is correct
2 Correct 143 ms 24280 KB Output is correct
3 Correct 211 ms 37224 KB Output is correct
4 Correct 196 ms 24216 KB Output is correct
5 Correct 229 ms 33796 KB Output is correct
6 Correct 162 ms 24216 KB Output is correct
7 Correct 197 ms 24216 KB Output is correct
8 Correct 147 ms 24216 KB Output is correct
9 Correct 265 ms 45252 KB Output is correct
10 Correct 347 ms 44224 KB Output is correct
11 Correct 403 ms 65180 KB Output is correct
12 Correct 435 ms 63028 KB Output is correct
13 Correct 150 ms 24216 KB Output is correct
14 Correct 10 ms 24216 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 24480 KB Output is correct
2 Correct 143 ms 24280 KB Output is correct
3 Correct 211 ms 37224 KB Output is correct
4 Correct 196 ms 24216 KB Output is correct
5 Correct 229 ms 33796 KB Output is correct
6 Correct 162 ms 24216 KB Output is correct
7 Correct 197 ms 24216 KB Output is correct
8 Correct 147 ms 24216 KB Output is correct
9 Correct 265 ms 45252 KB Output is correct
10 Correct 347 ms 44224 KB Output is correct
11 Correct 403 ms 65180 KB Output is correct
12 Correct 435 ms 63028 KB Output is correct
13 Correct 150 ms 24216 KB Output is correct
14 Correct 10 ms 24216 KB Output is correct
15 Correct 224 ms 24216 KB Output is correct
16 Correct 209 ms 24216 KB Output is correct
17 Correct 213 ms 24216 KB Output is correct
18 Correct 266 ms 34016 KB Output is correct
19 Correct 186 ms 24216 KB Output is correct
20 Correct 277 ms 34136 KB Output is correct
21 Correct 188 ms 24216 KB Output is correct
22 Correct 204 ms 24440 KB Output is correct
23 Correct 253 ms 48384 KB Output is correct
24 Correct 364 ms 47972 KB Output is correct
25 Correct 548 ms 70868 KB Output is correct
26 Correct 419 ms 66176 KB Output is correct
27 Correct 156 ms 24556 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 24480 KB Output is correct
2 Correct 143 ms 24280 KB Output is correct
3 Correct 211 ms 37224 KB Output is correct
4 Correct 196 ms 24216 KB Output is correct
5 Correct 229 ms 33796 KB Output is correct
6 Correct 162 ms 24216 KB Output is correct
7 Correct 197 ms 24216 KB Output is correct
8 Correct 147 ms 24216 KB Output is correct
9 Correct 265 ms 45252 KB Output is correct
10 Correct 347 ms 44224 KB Output is correct
11 Correct 403 ms 65180 KB Output is correct
12 Correct 435 ms 63028 KB Output is correct
13 Correct 150 ms 24216 KB Output is correct
14 Correct 10 ms 24216 KB Output is correct
15 Correct 224 ms 24216 KB Output is correct
16 Correct 209 ms 24216 KB Output is correct
17 Correct 213 ms 24216 KB Output is correct
18 Correct 266 ms 34016 KB Output is correct
19 Correct 186 ms 24216 KB Output is correct
20 Correct 277 ms 34136 KB Output is correct
21 Correct 188 ms 24216 KB Output is correct
22 Correct 204 ms 24440 KB Output is correct
23 Correct 253 ms 48384 KB Output is correct
24 Correct 364 ms 47972 KB Output is correct
25 Correct 548 ms 70868 KB Output is correct
26 Correct 419 ms 66176 KB Output is correct
27 Correct 156 ms 24556 KB Output is correct
28 Correct 275 ms 24216 KB Output is correct
29 Correct 269 ms 24288 KB Output is correct
30 Correct 429 ms 47560 KB Output is correct
31 Correct 230 ms 24280 KB Output is correct
32 Correct 338 ms 44992 KB Output is correct
33 Correct 300 ms 24356 KB Output is correct
34 Correct 247 ms 24388 KB Output is correct
35 Correct 214 ms 24392 KB Output is correct
36 Correct 345 ms 49616 KB Output is correct
37 Correct 494 ms 49484 KB Output is correct
38 Correct 586 ms 76352 KB Output is correct
39 Correct 588 ms 74368 KB Output is correct
40 Correct 253 ms 24628 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 24544 KB Output is correct
2 Correct 8 ms 24216 KB Output is correct
3 Correct 296 ms 24288 KB Output is correct
4 Correct 451 ms 33768 KB Output is correct
5 Correct 25 ms 24564 KB Output is correct
6 Correct 387 ms 26796 KB Output is correct
7 Correct 8 ms 24216 KB Output is correct
8 Correct 368 ms 24364 KB Output is correct
9 Correct 372 ms 24428 KB Output is correct
10 Correct 481 ms 51448 KB Output is correct
11 Correct 499 ms 50664 KB Output is correct
12 Correct 57 ms 24336 KB Output is correct
13 Correct 532 ms 49140 KB Output is correct
14 Correct 369 ms 24348 KB Output is correct
15 Correct 7 ms 24216 KB Output is correct
16 Correct 395 ms 24288 KB Output is correct
17 Correct 332 ms 24360 KB Output is correct
18 Correct 343 ms 24364 KB Output is correct
19 Correct 335 ms 24352 KB Output is correct
20 Correct 392 ms 24360 KB Output is correct
21 Correct 351 ms 24292 KB Output is correct
22 Correct 343 ms 24288 KB Output is correct
23 Correct 393 ms 24500 KB Output is correct
24 Correct 159 ms 24480 KB Output is correct
25 Correct 143 ms 24280 KB Output is correct
26 Correct 211 ms 37224 KB Output is correct
27 Correct 196 ms 24216 KB Output is correct
28 Correct 229 ms 33796 KB Output is correct
29 Correct 162 ms 24216 KB Output is correct
30 Correct 197 ms 24216 KB Output is correct
31 Correct 147 ms 24216 KB Output is correct
32 Correct 265 ms 45252 KB Output is correct
33 Correct 347 ms 44224 KB Output is correct
34 Correct 403 ms 65180 KB Output is correct
35 Correct 435 ms 63028 KB Output is correct
36 Correct 150 ms 24216 KB Output is correct
37 Correct 10 ms 24216 KB Output is correct
38 Correct 224 ms 24216 KB Output is correct
39 Correct 209 ms 24216 KB Output is correct
40 Correct 213 ms 24216 KB Output is correct
41 Correct 266 ms 34016 KB Output is correct
42 Correct 186 ms 24216 KB Output is correct
43 Correct 277 ms 34136 KB Output is correct
44 Correct 188 ms 24216 KB Output is correct
45 Correct 204 ms 24440 KB Output is correct
46 Correct 253 ms 48384 KB Output is correct
47 Correct 364 ms 47972 KB Output is correct
48 Correct 548 ms 70868 KB Output is correct
49 Correct 419 ms 66176 KB Output is correct
50 Correct 156 ms 24556 KB Output is correct
51 Correct 275 ms 24216 KB Output is correct
52 Correct 269 ms 24288 KB Output is correct
53 Correct 429 ms 47560 KB Output is correct
54 Correct 230 ms 24280 KB Output is correct
55 Correct 338 ms 44992 KB Output is correct
56 Correct 300 ms 24356 KB Output is correct
57 Correct 247 ms 24388 KB Output is correct
58 Correct 214 ms 24392 KB Output is correct
59 Correct 345 ms 49616 KB Output is correct
60 Correct 494 ms 49484 KB Output is correct
61 Correct 586 ms 76352 KB Output is correct
62 Correct 588 ms 74368 KB Output is correct
63 Correct 253 ms 24628 KB Output is correct
64 Correct 329 ms 24704 KB Output is correct
65 Correct 554 ms 50180 KB Output is correct
66 Correct 591 ms 46880 KB Output is correct
67 Correct 352 ms 24428 KB Output is correct
68 Correct 379 ms 24564 KB Output is correct
69 Correct 673 ms 75376 KB Output is correct
70 Correct 720 ms 66640 KB Output is correct
71 Correct 357 ms 29708 KB Output is correct
72 Correct 373 ms 25164 KB Output is correct