Submission #113255

#	Time	Username	Problem	Language	Result	Execution time	Memory
113255		imeimi2000	Two Transportations (JOI19_transportations)	C++17	100 / 100	2028 ms	85216 KiB

Azer

#include "Azer.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <iostream>
#define fs first
#define se second

using namespace std;
typedef pair<int, int> pii;

namespace {

const int inf = 1e9;
const int non = 505;
int n;
vector<pii> edge[2000];
int dist[2000];
queue<int> r;
priority_queue<pii> q;
int mode, mx, nd, nx;
int sync[2000];

}  // namespace

static int get(int bit) {
    int ret = 0;
    for (int i = 0; i < bit; ++i) {
        if (r.front()) ret |= 1 << i;
        r.pop();
    }
    return ret;
}

static void send(int x, int bit) {
    while (bit--) {
        SendA(x & 1);
        x >>= 1;
    }
}

static void sendNext() {
    nd = non + mx;
    while (!q.empty()) {
        int d, x;
        tie(d, x) = q.top();
        d = -d;
        if (dist[x] != d) {
            q.pop();
            continue;
        }
        if (sync[x]) {
            q.pop();
            for (pii i : edge[x]) {
                if (sync[i.fs]) continue;
                if (dist[i.fs] <= dist[x] + i.se) continue;
                dist[i.fs] = dist[x] + i.se;
                q.emplace(-dist[i.fs], i.fs);
            }
            continue;
        }
        nd = d;
        nx = x;
        break;
    }
    nd -= mx;
    send(nd, 9);
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n = N;
    for (int i = 0; i < A; ++i) {
        edge[U[i]].emplace_back(V[i], C[i]);
        edge[V[i]].emplace_back(U[i], C[i]);
    }
    for (int i = 1; i < n; ++i) dist[i] = inf;
    q.emplace(0, 0);
    sync[0] = 1;
    sendNext();
}

static void pro1() {
    int bd = get(9);
    if (nd == non && bd == non) return;
    if (nd < bd) {
        sync[nx] = 1;
        mx = dist[nx];
        send(nx, 11);
        sendNext();
    }
    else {
        mode = 1;
        mx += bd;
    }
}

static void pro2() {
    int bx = get(11);
    dist[bx] = mx;
    sync[bx] = 1;
    q.emplace(-dist[bx], bx);
    sendNext();
    mode = 0;
}

void ReceiveA(bool x) {
    r.push(x);
    if (mode == 0 && r.size() == 9) pro1();
    else if (mode == 1 && r.size() == 11) pro2();
}

vector<int> Answer() {
    vector<int> ans;
    for (int i = 0; i < n; ++i) ans.push_back(dist[i]);
    return ans;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <iostream>
#define fs first
#define se second

using namespace std;
typedef pair<int, int> pii;

namespace {

const int inf = 1e9;
const int non = 505;
int n;
vector<pii> edge[2000];
int dist[2000];
queue<int> r;
priority_queue<pii> q;
int mode, mx, nd, nx;
int sync[2000];

}  // namespace

static int get(int bit) {
    int ret = 0;
    for (int i = 0; i < bit; ++i) {
        if (r.front()) ret |= 1 << i;
        r.pop();
    }
    return ret;
}

static void send(int x, int bit) {
    while (bit--) {
        SendB(x & 1);
        x >>= 1;
    }
}

static void sendNext() {
    nd = non + mx;
    while (!q.empty()) {
        int d, x;
        tie(d, x) = q.top();
        d = -d;
        if (dist[x] != d) {
            q.pop();
            continue;
        }
        if (sync[x]) {
            q.pop();
            for (pii i : edge[x]) {
                if (sync[i.fs]) continue;
                if (dist[i.fs] <= dist[x] + i.se) continue;
                dist[i.fs] = dist[x] + i.se;
                q.emplace(-dist[i.fs], i.fs);
            }
            continue;
        }
        nd = d;
        nx = x;
        break;
    }
    nd -= mx;
    send(nd, 9);
}

void InitB(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n = N;
    for (int i = 0; i < A; ++i) {
        edge[U[i]].emplace_back(V[i], C[i]);
        edge[V[i]].emplace_back(U[i], C[i]);
    }
    for (int i = 1; i < n; ++i) dist[i] = inf;
    q.emplace(0, 0);
    sync[0] = 1;
    sendNext();
}

static void pro1() {
    int bd = get(9);
    if (nd == non && bd == non) return;
    if (nd <= bd) {
        sync[nx] = 1;
        mx = dist[nx];
        send(nx, 11);
        sendNext();
    }
    else {
        mode = 1;
        mx += bd;
    }
}

static void pro2() {
    int bx = get(11);
    dist[bx] = mx;
    sync[bx] = 1;
    q.emplace(-dist[bx], bx);
    sendNext();
    mode = 0;
}

void ReceiveB(bool x) {
    r.push(x);
    if (mode == 0 && r.size() == 9) pro1();
    else if (mode == 1 && r.size() == 11) pro2();
}

• 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