oj.uz

Submission #785919

# Submission time Handle Problem Language Result Execution time Memory
785919 2023-07-17T19:08:06 Z Piokemon Two Transportations (JOI19_transportations) C++17
0 / 100
 474 ms 13308 KB 
#include <bits/stdc++.h>
#include "Azer.h"
using namespace std;
typedef long long int ll;
    
namespace {
int n;
vector<pair<int,int>> graf[2009];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> djikstra;
int dst[2009];
int wczyt=0,ter=0;
pair<int,int> cel;
int nr=0;
    
void napisz(int x, int cnt){
    for (int i=0;i<cnt;i++) SendA(x & (1<<i));
}
    
void nast(int v, int d){
    //if (nr<10) cout << "A:" << v << ' ' << d << ' ' << djikstra.size() << '\n';
    dst[v] = d;
    for (pair<int,int> x:graf[v]){
        if (dst[x.first] > d+x.second){
            dst[x.first] = d+x.second;
            djikstra.push({dst[x.first],x.first});
        }
    }
    while(!djikstra.empty() && dst[djikstra.top().second] < djikstra.top().first) djikstra.pop();
    if (djikstra.empty()){
        djikstra.push({(1<<20)-1,1});
        //if (nr<10) cout << "A empty\n";
    }
    //if (nr<10) cout << "A->B " << djikstra.top().first << ' ' << djikstra.top().second << '\n';
    napisz(djikstra.top().first,20);
    napisz(djikstra.top().second,11);
    nr++;
}
    
}  // namespace
    
    
void InitA(int N, int A, vector<int> U, vector<int> V,
            vector<int> C) {
    n = N;
    for (int x=0;x<A;x++){
        graf[U[x]].push_back({V[x],C[x]});
        graf[V[x]].push_back({U[x],C[x]});
    }
    for (int x=0;x<=n;x++) dst[x] = 1e9+9;
    nast(0,0);
    cel = {-1,-1};
}
    
void ReceiveA(bool x) {
    wczyt += (1<<ter) * x;
    ter++;
    if (ter==20){
        cel.second = wczyt;
        wczyt = 0;
        ter = 0;
    }
    if (ter==11 && cel.second != -1){
        cel.first = wczyt;
        //if (nr<10) cout << "A ma:" << djikstra.top().first << ' ' << cel.second << '\n';
        //if (nr<10) cout << "A dostalo: " << cel.first << ' ' << cel.second << '\n';
        //if (nr<10) cout << "A twierdzi o empt:  " << apuste << ' ' << bpuste << '\n';
        if (nr>=n) return;
        if (djikstra.top().first <= cel.second){
            cel.second = djikstra.top().first;
            cel.first = djikstra.top().second;
            djikstra.pop();
            //if (nr<10) cout << "hi\n";
        }
        nast(cel.first,cel.second);
        cel = {-1,-1};
        ter = 0;
        wczyt = 0;
    }
}
    
vector<int> Answer() {
    vector<int> odp;
    for (int x=0;x<n;x++) odp.push_back(dst[x]);
    return odp;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
    
namespace {
int n;
vector<pair<int,int>> graf[2009];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> djikstra;
int dst[2009];
int wczyt=0,ter=0;
pair<int,int> cel;
pair<int,int> wczes;
int nr=0;

void napisz(int x, int cnt){
    for (int i=0;i<cnt;i++) SendB(x & (1<<i));
}
    
void nast(int v, int d){
    //if (nr<10) cout << "B:" << v << ' ' << d << '\n';
    dst[v] = d;
    //if (nr<10) cout << "lelum " << poprz << ' ' << d << '\n';
    for (pair<int,int> x:graf[v]){
        if (dst[x.first] > d+x.second){
            dst[x.first] = d+x.second;
            djikstra.push({dst[x.first],x.first});
        }
    }
    while(!djikstra.empty() && dst[djikstra.top().second] < djikstra.top().first) djikstra.pop();
    if (djikstra.empty()){
        djikstra.push({(1<<20)-1,1});
    }
    //if (nr<10) cout << "B->A " << djikstra.top().first << ' ' << djikstra.top().second << '\n';
    napisz(djikstra.top().first,20);
    napisz(djikstra.top().second,11);
    nr++;
}
    
}  // namespace
    
    
    
void InitB(int N, int B, vector<int> S, vector<int> T,
            vector<int> D) {
    n = N;
    for (int x=0;x<B;x++){
        graf[T[x]].push_back({S[x],D[x]});
        graf[S[x]].push_back({T[x],D[x]});
    }
    for (int x=0;x<=n;x++) dst[x] = 1e9+9;
    cel = {-1,-1};
    wczes = {0,0};
}
    
void ReceiveB(bool y) {
    wczyt += (1<<ter) * y;
    ter++;
    if (ter==20){
        cel.second = wczyt;
        wczyt = 0;
        ter = 0;
    }
    if (ter==11 && cel.second != -1){
        if (nr>=n) return;
        //if (nr<10) cout << "B jestem debilem: " << poprz << '\n';
        nast(wczes.first,wczes.second);
        cel.first = wczyt;
        //if (nr<10) cout << "B dostalo: " << cel.first << ' ' << cel.second << '\n';
        //if (nr<10) cout << "nr 2: " << apuste << ' ' << bpuste << '\n';
        if (djikstra.top().first < cel.second){
            cel.second = djikstra.top().first;
            cel.first = djikstra.top().second;
            djikstra.pop();
        }
        wczes = cel;
        cel = {-1,-1};
        ter = 0;
        wczyt = 0;
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 336 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 2 ms 656 KB Output is correct
2 Runtime error 199 ms 416 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 684 KB Output is correct
2 Correct 340 ms 720 KB Output is correct
3 Incorrect 474 ms 13308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 684 KB Output is correct
2 Correct 340 ms 720 KB Output is correct
3 Incorrect 474 ms 13308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 684 KB Output is correct
2 Correct 340 ms 720 KB Output is correct
3 Incorrect 474 ms 13308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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