oj.uz

Submission #785934

# Submission time Handle Problem Language Result Execution time Memory
785934 2023-07-17T19:24:14 Z Piokemon Two Transportations (JOI19_transportations) C++17
38 / 100
 703 ms 38436 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){
            djikstra.push({d+x.second,x.first});
        }
    }
    while(!djikstra.empty() && dst[djikstra.top().second] < 1e9) djikstra.pop();
    if (djikstra.empty()){
        djikstra.push({(1<<20)-1,0});
        //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 (min(djikstra.top().first,cel.second) == (1<<20)-1) 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){
            djikstra.push({d+x.second,x.first});
        }
    }
    while(!djikstra.empty() && dst[djikstra.top().second] < 1e9) djikstra.pop();
    if (djikstra.empty()){
        djikstra.push({(1<<20)-1,0});
    }
    //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};
    djikstra.push({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<10) cout << "B jestem debilem: " << poprz << '\n';
        nast(wczes.first,wczes.second);
        if (min(djikstra.top().first,cel.second) == (1<<20)-1) return;
        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 217 ms 328 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 191 ms 456 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 118 ms 328 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 692 KB Output is correct
2 Correct 304 ms 656 KB Output is correct
3 Correct 485 ms 13308 KB Output is correct
4 Correct 337 ms 716 KB Output is correct
5 Correct 512 ms 10104 KB Output is correct
6 Correct 235 ms 696 KB Output is correct
7 Correct 399 ms 656 KB Output is correct
8 Correct 440 ms 724 KB Output is correct
9 Correct 544 ms 19552 KB Output is correct
10 Correct 537 ms 19512 KB Output is correct
11 Correct 703 ms 38436 KB Output is correct
12 Correct 700 ms 35928 KB Output is correct
13 Correct 381 ms 656 KB Output is correct
14 Correct 2 ms 656 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 692 KB Output is correct
2 Correct 304 ms 656 KB Output is correct
3 Correct 485 ms 13308 KB Output is correct
4 Correct 337 ms 716 KB Output is correct
5 Correct 512 ms 10104 KB Output is correct
6 Correct 235 ms 696 KB Output is correct
7 Correct 399 ms 656 KB Output is correct
8 Correct 440 ms 724 KB Output is correct
9 Correct 544 ms 19552 KB Output is correct
10 Correct 537 ms 19512 KB Output is correct
11 Correct 703 ms 38436 KB Output is correct
12 Correct 700 ms 35928 KB Output is correct
13 Correct 381 ms 656 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Runtime error 223 ms 372 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 692 KB Output is correct
2 Correct 304 ms 656 KB Output is correct
3 Correct 485 ms 13308 KB Output is correct
4 Correct 337 ms 716 KB Output is correct
5 Correct 512 ms 10104 KB Output is correct
6 Correct 235 ms 696 KB Output is correct
7 Correct 399 ms 656 KB Output is correct
8 Correct 440 ms 724 KB Output is correct
9 Correct 544 ms 19552 KB Output is correct
10 Correct 537 ms 19512 KB Output is correct
11 Correct 703 ms 38436 KB Output is correct
12 Correct 700 ms 35928 KB Output is correct
13 Correct 381 ms 656 KB Output is correct
14 Correct 2 ms 656 KB Output is correct
15 Runtime error 223 ms 372 KB Execution killed with signal 13
16 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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