Submission #748618

#	Time	Username	Problem	Language	Result	Execution time	Memory
748618		piOOE	Two Transportations (JOI19_transportations)	C++17	100 / 100	734 ms	48896 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58001;
    constexpr int inf = 1e9 + 7;

    int N, A, Q = 0, S = 0, Last = 0, usedCnt = 0;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];

    void upd(int v) {
        for (auto [to, w]: adj[v]) {
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
    }

    void ckmin(int v, int d) {
        if (dist[v] > d) {
            st.erase({dist[v], v});
            st.emplace(dist[v] = d, v);
//            upd(v);
        }
    }
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    ::N = N, ::A = A;

    for (int i = 0; i < A; ++i) {
        adj[U[i]].emplace_back(V[i], C[i]);
        adj[V[i]].emplace_back(U[i], C[i]);
    }

    fill(dist, dist + N, inf);

    ckmin(0, 0);

    for (int i = 0; i < 9; ++i) {
        SendA(0);
    }
}

void ReceiveA(bool x) {
    b[Q++] = x;

    if (Q - Last == 9) {
        int nd = 0;

        for (int i = 0; i < 9; ++i) {
            nd |= b[Last + i] << i;
        }

        if (nd > 500) {
            auto [d, v] = *st.begin();
            st.erase(st.begin());

            upd(v);
            assert(!used[v]);
            used[v] = true;
            usedCnt += 1;
            S = d;

            for (int i = 0; i < 11; ++i) {
                SendA(v >> i & 1);
            }

            Last = Q;
        }
    } else if (Q - Last == 9 + 11) {
        int nd = 0, v = 0;

        for (int i = 0; i < 9; ++i) {
            nd |= b[Last + i] << i;
        }
        for (int i = 0; i < 11; ++i) {
            v |= b[Last + i + 9] << i;
        }

        assert(!used[v]);
        used[v] = true;
        usedCnt += 1;
        ckmin(v, S + nd);
        upd(v);
        st.erase({dist[v], v});
        S += nd;
        Last = Q;
    }

    if (Q == Last) {
        if (usedCnt == N) {
            return;
        } else if (st.empty()) {
            for (int i = 0; i < 9; ++i) {
                SendA(1);
            }
            return;
        }

        int d = st.begin()->first - S;

        for (int i = 0; i < 9; ++i) {
            SendA(d >> i & 1);
        }
    }
}

std::vector<int> Answer() {
    std::vector<int> ans(N);
    for (int k = 0; k < N; ++k) {
        ans[k] = dist[k];
    }
    return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58000;
    constexpr int inf = 1e9 + 7;

    int N, B, Q = 0, S = 0, Last = 0;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];

    void upd(int v) {
        for (auto [to, w]: adj[v]) {
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
    }

    void ckmin(int v, int d) {
        if (dist[v] > d) {
            st.erase({dist[v], v});
            st.emplace(dist[v] = d, v);
//            upd(v);
        }
    }
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    ::N = N, ::B = B;

    fill(dist, dist + N, inf);

    for (int i = 0; i < B; ++i) {
        adj[S[i]].emplace_back(T[i], D[i]);
        adj[T[i]].emplace_back(S[i], D[i]);
    }
}

void ReceiveB(bool y) {
    b[Q++] = y;

    if ((Q - Last) == 9) {
        int d = 0;

        for (int i = 0; i < 9; ++i) {
            d |= b[Last + i] << i;
        }

//        cout << st.size() << endl;

        int nd = st.empty() ? inf : st.begin()->first - S;
        assert(nd >= 0);

        if (nd < d) {
            int v = st.begin()->second;
            st.erase(st.begin());
            upd(v);
            assert(!used[v]);
            used[v] = true;

            for (int i = 0; i < 9; ++i) {
                SendB(nd >> i & 1);
            }
            for (int i = 0; i < 11; ++i) {
                SendB(v >> i & 1);
            }

            S += nd;
            Last = Q;
        } else {
            for (int i = 0; i < 9; ++i) {
                SendB(1);
            }
        }
    } else if (Q - Last == 9 + 11) {
        int d = 0, v = 0;

        for (int i = 0; i < 9; ++i) {
            d |= b[Last + i] << i;
        }
        for (int i = 0; i < 11; ++i) {
            v |= b[Last + 9 + i] << i;
        }

        ckmin(v, S + d);
        used[v] = true;
        st.erase({dist[v], v});
        upd(v);

        S += d;

        Last = Q;
    }
}

• 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