oj.uz

Submission #789539

# Submission time Handle Problem Language Result Execution time Memory
789539 2023-07-21T13:21:16 Z someone Two Transportations (JOI19_transportations) C++14
38 / 100
 550 ms 35612 KB 
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

struct Arc {
    int nex, pds;
};

const int N = 2e3 + 42, INF = 1e6 + 42;

int n, knows[N];
vector<bool> msg;
vector<int> dist;
vector<Arc> arc[N];
priority_queue<pair<int, int>> pq;

void send(int i, int d) {
    for(int j = 0; j < 11; j++)
        SendA(i & (1 << j));
    for(int j = 0; j < 20; j++)
        SendA(d & (1 << j));
}

void InitA(int X, int a, vector<int> U, vector<int> V, vector<int> C) {
    //cout << '\n' << '\n';
    n = X;
    dist.resize(n);
    for(int i = 0; i < a; i++) {
        arc[U[i]].push_back({V[i], C[i]});
        arc[V[i]].push_back({U[i], C[i]});
    }
    for(int i = 1; i < n; i++)
        knows[i] = dist[i] = INF;
    for(int i = 0; i < n; i++)
        pq.push({-dist[i], i});

    send(0, 0);
}

void ReceiveA(bool x) {
    msg.push_back(x);
    if(31 == (int)msg.size()) {
        int i = 0, d = 0;
        for(int j = 0; j < 11; j++)
            i += (1 << j) * msg[j];
        for(int j = 0; j < 20; j++)
            d += (1 << j) * msg[j + 11];
        msg.clear();

        if(d < dist[i]) {
            dist[i] = d;
            pq.push({-d, i});
        }
        knows[i] = d;

        bool envoi = false;
        while(!envoi && !pq.empty()) {
            i = pq.top().second,
            d = -pq.top().first;
            pq.pop();
            if(dist[i] == d) {
                for(Arc a : arc[i]) {
                    if(dist[a.nex] > dist[i] + a.pds) {
                        dist[a.nex] = dist[i] + a.pds;
                        pq.push({-dist[a.nex], a.nex});
                    }
                }
                if(knows[i] > d) {
                    //cout << "Azer envoie " << i << ' ' << d << '\n';
                    knows[i] = d;
                    envoi = true;
                    send(i, d);
                }
            }
        }
        if(!envoi)
            for(int j = 0; j < n; j++)
                if(dist[j] == INF) {
                    //cout << "Azer n'envoie rien\n";
                    send(j, INF);
                    j = n;
                }
    }
}

vector<int> Answer() {
    return dist;
}

#include <bits/stdc++.h>
#include "Baijan.h"
using namespace std;

struct Arc {
    int nex, pds;
};

const int N = 2e3 + 42, INF = 1e6 + 42;

int n, knows[N];
vector<int> dist;
vector<Arc> arc[N];
vector<bool> msg;
priority_queue<pair<int, int>> pq;

void send(int i, int d) {
    for(int j = 0; j < 11; j++)
        SendB(i & (1 << j));
    for(int j = 0; j < 20; j++)
        SendB(d & (1 << j));
}

void InitB(int X, int b, vector<int> S, vector<int> T, vector<int> D) {
    n = X;
    dist.resize(n);
    for(int i = 0; i < b; i++) {
        arc[S[i]].push_back({T[i], D[i]});
        arc[T[i]].push_back({S[i], D[i]});
    }
    for(int i = 1; i < n; i++)
        knows[i] = dist[i] = INF;
    for(int i = 0; i < n; i++)
        pq.push({-dist[i], i});
}

void ReceiveB(bool y) {
    msg.push_back(y);
    if(31 == (int)msg.size()) {
        int i = 0, d = 0;
        for(int j = 0; j < 11; j++)
            i += (1 << j) * msg[j];
        for(int j = 0; j < 20; j++)
            d += (1 << j) * msg[j + 11];
        msg.clear();

        if(d < dist[i]) {
            dist[i] = d;
            pq.push({-d, i});
        }
        knows[i] = d;

        bool envoi = false;
        while(!envoi && !pq.empty()) {
            i = pq.top().second,
            d = -pq.top().first;
            pq.pop();
            if(dist[i] == d) {
                for(Arc a : arc[i]) {
                    if(dist[a.nex] > dist[i] + a.pds) {
                        dist[a.nex] = dist[i] + a.pds;
                        pq.push({-dist[a.nex], a.nex});
                    }
                }
                if(knows[i] > d) {
                    knows[i] = d;
                    //cout << "Baijan envoie " << i << ' ' << d << '\n';
                    envoi = true;
                    send(i, d);
                }
            }
        }
        if(!envoi)
            for(int j = 0; j < n; j++)
                if(dist[j] == INF) {
                    //cout << "Baijan n'envoie rien\n";
                    send(j, INF);
                    j = n;
                }
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 249 ms 380 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 1 ms 656 KB Output is correct
2 Runtime error 184 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 Runtime error 233 ms 468 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 215 ms 708 KB Output is correct
2 Correct 414 ms 760 KB Output is correct
3 Correct 336 ms 13320 KB Output is correct
4 Correct 376 ms 656 KB Output is correct
5 Correct 251 ms 10108 KB Output is correct
6 Correct 147 ms 788 KB Output is correct
7 Correct 282 ms 656 KB Output is correct
8 Correct 251 ms 656 KB Output is correct
9 Correct 477 ms 18088 KB Output is correct
10 Correct 550 ms 18216 KB Output is correct
11 Correct 373 ms 35612 KB Output is correct
12 Correct 319 ms 30636 KB Output is correct
13 Correct 140 ms 656 KB Output is correct
14 Correct 1 ms 656 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 708 KB Output is correct
2 Correct 414 ms 760 KB Output is correct
3 Correct 336 ms 13320 KB Output is correct
4 Correct 376 ms 656 KB Output is correct
5 Correct 251 ms 10108 KB Output is correct
6 Correct 147 ms 788 KB Output is correct
7 Correct 282 ms 656 KB Output is correct
8 Correct 251 ms 656 KB Output is correct
9 Correct 477 ms 18088 KB Output is correct
10 Correct 550 ms 18216 KB Output is correct
11 Correct 373 ms 35612 KB Output is correct
12 Correct 319 ms 30636 KB Output is correct
13 Correct 140 ms 656 KB Output is correct
14 Correct 1 ms 656 KB Output is correct
15 Correct 233 ms 808 KB Output is correct
16 Runtime error 144 ms 424 KB Execution killed with signal 13
17 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 708 KB Output is correct
2 Correct 414 ms 760 KB Output is correct
3 Correct 336 ms 13320 KB Output is correct
4 Correct 376 ms 656 KB Output is correct
5 Correct 251 ms 10108 KB Output is correct
6 Correct 147 ms 788 KB Output is correct
7 Correct 282 ms 656 KB Output is correct
8 Correct 251 ms 656 KB Output is correct
9 Correct 477 ms 18088 KB Output is correct
10 Correct 550 ms 18216 KB Output is correct
11 Correct 373 ms 35612 KB Output is correct
12 Correct 319 ms 30636 KB Output is correct
13 Correct 140 ms 656 KB Output is correct
14 Correct 1 ms 656 KB Output is correct
15 Correct 233 ms 808 KB Output is correct
16 Runtime error 144 ms 424 KB Execution killed with signal 13
17 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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