Submission #583145

#	Time	Username	Problem	Language	Result	Execution time	Memory
583145		Johann	Two Transportations (JOI19_transportations)	C++14	100 / 100	889 ms	57720 KiB

Azer

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

#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

namespace {

    const int maxn = 2005;
    const int LENV = 11;
    const int LEND = 9;
    int n, maxD = 0;
    vi dist(maxn, INT_MAX);
    vpii adj[maxn];
    int phase;
    priority_queue<pii, vpii, greater<pii>> q;


    int getMinD() {
        while (!q.empty() && q.top().first >= dist[q.top().second]) q.pop();
        if (q.empty()) return ((1 << LEND) - 1);
        return q.top().first - maxD;
    }
    int getMinV() { return (!q.empty()) ? q.top().second : -1; }
// may call SendA()
    void send(int m, int len) {
        // cout << "A Send: " << m << endl;
        for (int i = len-1; i >= 0; --i) SendA((m>>i)&1);
    }
// Variables for ...
    int d,cntD=0; // receiving distances
    int v,cntV=0; // receiving points
    int cntN=0; // counting the

    void addVertexWithDist(int vv, int dd) {
        // cout << "A add V " << vv << " mit Dist " << dd << endl;
        dist[vv] = dd;
        maxD = dd;

        ++cntN;
        if (cntN == n) return;

        int u,c;
        for (pii e : adj[vv]) {
            tie(u,c) = e;
            q.push({ dist[vv] + c, u });
        }

        // cout << "A dists: "; for (int i=0;i<n;++i) cout << dist[i] << " "; cout << endl;
        send(getMinD(), LEND);
        phase = LEND;
        d = 0;
    }
    void receiveD(bool x) {
        d = (d << 1) + x;
        ++cntD;
        if (cntD == LEND) {
            // cout << "A Receive (d: " << d << ")" << endl;
            cntD = 0;
            if (d < getMinD()) { // Aufpassen mit < und <= in der anderen Datei.
                // cout << "A receive: Erhalten kleiner als jetzt" << endl;
                phase = LENV;
                v = 0;
                // rest folgt in receive V
            } else {
                // cout << "A receive: Erhalten größer gleich jetzt" << endl;
                int vv = getMinV();
                int dd = maxD + getMinD();
                q.pop();
                send(vv, LENV);
                addVertexWithDist(vv, dd); // starts new iteration
            }
        }
    }
    void receiveV(bool x) {
        v = (v << 1) + x;
        ++cntV;
        if (cntV == LENV) {
            // cout << "A Receive (v: " << v << endl;
            cntV = 0;
            addVertexWithDist(v, maxD + d);
        }
    }

}  // namespace

void ReceiveA(bool x) {
    if (phase == LEND) { // Distance
        receiveD(x);
    } else { // Knoten
        receiveV(x);
    }
}
void InitA(int N, int A, vi U, vi V, vi C) {
    n = N;
    dist.resize(n);
    for (int i = 0; i < A; ++i) {
        adj[U[i]].push_back({ V[i], C[i] });
        adj[V[i]].push_back({ U[i], C[i] });
    }
    addVertexWithDist(0, 0);
}
vi Answer() {
    return dist;
}

Baijan

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

#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

namespace {

    const int maxn = 2005;
    const int LENV = 11;
    const int LEND = 9;
    int n, maxD = 0;
    vi dist(maxn, INT_MAX);
    vpii adj[maxn];
    int phase;
    priority_queue<pii, vpii, greater<pii>> q;


    int getMinD() {
        while (!q.empty() && q.top().first >= dist[q.top().second]) q.pop();
        if (q.empty()) return ((1 << LEND) - 1);
        return q.top().first - maxD;
    }
    int getMinV() { return (!q.empty()) ? q.top().second : -1; }
// may call SendB()
    void send(int m, int len) {
        // cout << "B Send: " << m << endl;
        for (int i = len-1; i >= 0; --i) {
            SendB((m>>i)&1);
        }
    }
// Variables for ...
    int d,cntD=0; // receiving distances
    int v,cntV=0; // receiving points
    int cntN=0; // counting the

    void addVertexWithDist(int vv, int dd) {
        // cout << "B bet V " << vv << " mit Dist " << dd << endl;
        dist[vv] = dd;
        maxD = dd;

        ++cntN;
        if (cntN == n) return;

        int u,c;
        for (pii e : adj[vv]) {
            tie(u,c) = e;
            q.push({ dist[vv] + c, u });
        }

        // cout << "B dists: "; for (int i=0;i<n;++i) cout << dist[i] << " "; cout << endl;
        send(getMinD(), LEND);
        phase = LEND;
        d = 0;
    }
    void receiveD(bool x) {
        d = (d << 1) + x;
        ++cntD;
        if (cntD == LEND) {
            // cout << "B Receive (d: " << d << ")" << endl;
            cntD = 0;
            if (getMinD() < d) { // Aufpassen mit < und <= in der anderen Datei.
                // cout << "B receive: Erhalten größer gleich jetzt" << endl;
                int vv = getMinV();
                int dd = maxD + getMinD();
                q.pop();
                send(vv, LENV);
                addVertexWithDist(vv, dd); // starts new iteration
            } else {
                // cout << "B receive: Erhalten kleiner als jetzt" << endl;
                phase = LENV;
                v = 0;
                // rest folgt in receive V
            }
        }
    }
    void receiveV(bool x) {
        v = (v << 1) + x;
        ++cntV;
        if (cntV == LENV) {
            // cout << "B Receive (v: " << v << endl;
            cntV = 0;
            addVertexWithDist(v, maxD + d);
        }
    }

}  // namespace

void ReceiveB(bool x) {
    if (phase == LEND) { // Distance
        receiveD(x);
    } else { // Knoten
        receiveV(x);
    }
}
void InitB(int N, int A, vi U, vi V, vi C) {
    n = N;
    dist.resize(n);
    for (int i = 0; i < A; ++i) {
        adj[U[i]].push_back({ V[i], C[i] });
        adj[V[i]].push_back({ U[i], C[i] });
    }
    addVertexWithDist(0, 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