제출 #915882

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915882		gawr_gura	Two Transportations (JOI19_transportations)	C++17	100 / 100	679 ms	49080 KiB

Azer

#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);
                        }
                }
        }
        for (int i = 0; i < N; i++) {
                if (done[i] == 0) {
                        send_nude(max_until_now + 511, 0);
                        return;
                }
        }
}

}  // 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;
}

Baijan

#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::max_until_now = b::d[b::pos];
                        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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16