oj.uz

Submission #915874

# Submission time Handle Problem Language Result Execution time Memory
915874 2024-01-24T20:13:41 Z gawr_gura Two Transportations (JOI19_transportations) C++17
14 / 100
 489 ms 27884 KB 
#include "Azer.h"

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

namespace a {

int N;
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>> pq;
vector<int> d;
vector<int> done;
int max_until_now = 0;
bool receive_length = 0;
int cnt_length;
int length, length_a;
int pos, cnt_pos;
int a;

void send_nude(int du, int u) {
        // cerr << du << ' ' << u << '\n';
        length_a = du - max_until_now;
        a = u;
        // cerr << "now sending length " << length_a << " from a to b!\n";
        for (int i = 0; i < 9; i++) SendA(length_a >> i & 1);
        receive_length = 1;
        cnt_length = length = 0;
}

void try_next() {
        while (pq.size()) {
                auto [du, u] = pq.top();
                // cerr << "pq : " << du << ' ' << u << '\n';
                if (done[u] == 0) {
                        send_nude(-du, u);
                        return;
                }
                pq.pop();
                // cerr << d[u] << '\n';
                if (-du != d[u]) continue;
                max_until_now = -du;
                for (auto [v, w] : adj[u]) {
                        if (d[v] > d[u] + w) {
                                d[v] = d[u] + w;
                                pq.emplace(-d[v], v);
                        }
                }
        }
        send_nude(max_until_now + 511, 0);
}

}  // namespace a
void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
        a::N = N;
        a::adj.resize(N);
        a::d.assign(N, 1e9);
        a::done.assign(N, 0);
        for (int i = 0; i < A; i++) a::adj[U[i]].emplace_back(V[i], C[i]);
        for (int i = 0; i < A; i++) a::adj[V[i]].emplace_back(U[i], C[i]);
        a::pq.emplace(0, 0);
        a::d[0] = 0;
        a::done[0] = 1;
        a::try_next();
}

void ReceiveA(bool x) {
        if (a::receive_length) {
                a::length |= x << a::cnt_length;
                a::cnt_length++;
                if (a::cnt_length == 9) {
                        // cerr << "now receiving length " << a::length << " from b to a\n";
                        if (a::length < a::length_a) {
                                a::length += a::max_until_now;
                                a::pos = a::cnt_pos = 0;
                                a::receive_length = 0;
                        } else {
                                // cerr << "now sending pos " << a::a << " from a to b!\n";
                                for (int i = 0; i < 11; i++) SendA(a::a >> i & 1);
                                a::done[a::a] = 1;
                                a::try_next();
                        }
                }
        } else {
                a::pos |= x << a::cnt_pos;
                a::cnt_pos++;
                if (a::cnt_pos == 11) {
                        // cerr << a::max_until_now << '\n';
                        // cerr << "now receiving pos " << a::pos << " from b to a!\n";
                        a::done[a::pos] = 1;
                        a::d[a::pos] = a::length;
                        a::pq.emplace(-a::length, a::pos);
                        a::try_next();
                }
        }
}

std::vector<int> Answer() {
        return a::d;
}

#include "Baijan.h"

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

namespace b {

int N;
int x = 0;
vector<vector<pair<int, int>>> adj;
priority_queue<pair<int, int>> pq;
vector<int> d;
vector<int> done;
int length, cnt_length;
bool receive_length;
int length_b;
int max_until_now;
int pos, cnt_pos;

void send_nude(int du, int u) {
        // cerr << "send_nude on b: " << du << ' ' << u << '\n';
        int length_b = du - max_until_now;
        // cerr << "now sending " << length_b << " from b to a!\n";
        for (int i = 0; i < 9; i++) SendB(length_b >> i & 1);
        if (length_b < length) {
                for (int i = 0; i < 11; i++) SendB(u >> i & 1);
                done[u] = 1;
                length = cnt_length = 0;
                receive_length = 1;
        } else {
                receive_length = 0;
                pos = 0, cnt_pos = 0;
        }
}

}  // namespace b

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
        b::N = N;
        b::adj.resize(N);
        b::d.assign(N, 1e9);
        b::done.assign(N, 0);
        for (int i = 0; i < B; i++) b::adj[S[i]].emplace_back(T[i], D[i]);
        for (int i = 0; i < B; i++) b::adj[T[i]].emplace_back(S[i], D[i]);
        b::pq.emplace(0, 0);
        b::d[0] = 0;
        b::done[0] = 1;
        b::max_until_now = 0;
        b::receive_length = 1;
        b::length = b::cnt_length = 0;
}

void ReceiveB(bool y) {
        if (b::receive_length) {
                b::length |= y << b::cnt_length;
                b::cnt_length++;
                if (b::cnt_length == 9) {
                        bool ok = 1;
                        for (int i = 0; i < b::N; i++) ok &= b::done[i];
                        // cerr << "now receiving length " << b::length << " from a to b\n";
                        while (b::pq.size()) {
                                auto [du, u] = b::pq.top();
                                if (b::done[u] == 0) {
                                        b::send_nude(-du, u);
                                        ok = 1;
                                        break;
                                }
                                b::pq.pop();
                                if (-du != b::d[u]) continue;
                                b::max_until_now = -du;
                                for (auto&& [v, w] : b::adj[u]) {
                                        if (b::d[v] > b::d[u] + w) {
                                                b::d[v] = b::d[u] + w;
                                                b::pq.emplace(-b::d[v], v);
                                        }
                                }
                        }
                        if (!ok) b::send_nude(b::max_until_now + 511, 0);
                }
        } else {
                b::pos |= y << b::cnt_pos;
                b::cnt_pos++;
                if (b::cnt_pos == 11) {
                        // cerr << "now receiving pos " << b::pos << " from a to b!\n";
                        b::d[b::pos] = b::length + b::max_until_now;
                        b::pq.emplace(-b::d[b::pos], b::pos);
                        b::done[b::pos] = 1;
                        b::receive_length = 1;
                        b::cnt_length = b::length = 0;
                }
        }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 1060 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 284 ms 1060 KB Output is correct
4 Correct 371 ms 10432 KB Output is correct
5 Correct 12 ms 920 KB Output is correct
6 Correct 320 ms 2336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 664 KB Output is correct
2 Correct 313 ms 884 KB Output is correct
3 Correct 383 ms 940 KB Output is correct
4 Correct 468 ms 27884 KB Output is correct
5 Correct 489 ms 24536 KB Output is correct
6 Correct 71 ms 916 KB Output is correct
7 Correct 470 ms 24668 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 1060 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 284 ms 1060 KB Output is correct
4 Correct 371 ms 10432 KB Output is correct
5 Correct 12 ms 920 KB Output is correct
6 Correct 320 ms 2336 KB Output is correct
7 Correct 0 ms 664 KB Output is correct
8 Correct 313 ms 884 KB Output is correct
9 Correct 383 ms 940 KB Output is correct
10 Correct 468 ms 27884 KB Output is correct
11 Correct 489 ms 24536 KB Output is correct
12 Correct 71 ms 916 KB Output is correct
13 Correct 470 ms 24668 KB Output is correct
14 Incorrect 367 ms 876 KB Output isn't correct
15 Halted 0 ms 0 KB -