Submission #1189292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189292		12345678	Two Transportations (JOI19_transportations)	C++20	38 / 100	3127 ms	35488 KiB

Azer

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

using namespace std;

namespace {
    const int nx=2e3+5, inf=1e9, mx=1e6+5;

    int n, mn[nx], vs[nx], w, u, cnt, exp, sz[mx], qry;
    vector<pair<int, int>> d[nx];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> pq;
    vector<int> in;
    pair<int, int> da, db;

    void sendtop()
    {
        if (cnt>n) return;
        qry+=sz[cnt]+11;
        if (qry>29000)
        {
            while (1)
            {

            }
        }
        while (!pq.empty()&&vs[pq.top().second]) pq.pop();
        if (pq.empty()) for (int i=0; i<sz[cnt]+11; i++) SendA(1);
        else
        {
            auto [w, u]=pq.top();
            for (int i=0; i<sz[cnt]; i++) SendA(w&(1<<i));
            for (int i=0; i<11; i++) SendA(u&(1<<i));
        }
    }
} 

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n=N;
    for (int i=1; i<N; i++) mn[i]=inf;
    for (int i=0; i<A; i++) d[U[i]].push_back({V[i], C[i]}), d[V[i]].push_back({U[i], C[i]});
    pq.push({0, 0});
    cnt=1;
    for (int i=1; i<=n; i++) sz[i]=ceil(log2(500*i));
    sendtop();
}

void ReceiveA(bool x) {
    in.push_back(x);
    if (in.size()<11+sz[cnt]) return;
    db={0, 0};
    for (int i=0; i<sz[cnt]; i++) db.first|=(in[i]<<i);
    for (int i=0; i<11; i++) db.second|=(in[sz[cnt]+i]<<i);
    in.clear();
    da=pq.empty()?make_pair(INT_MAX, INT_MAX):pq.top();
    auto [w, u]=min(da, db);
    if (u>=n) return;
    mn[u]=w;
    vs[u]=1;
    for (auto [v, cw]:d[u]) if (!vs[v]&&w+cw<mn[v]) mn[v]=w+cw, pq.push({w+cw, v});
    cnt++;
    sendtop();
}

std::vector<int> Answer() {
    std::vector<int> ans(n);
    for (int i=0; i<n; i++) ans[i]=mn[i];
    return ans;
}

Baijan

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

using namespace std;

namespace {
    const int nx=2e3+5, inf=1e9, mx=1e6+5;

    int n, mn[nx], vs[nx], w, u, cnt, exp, sz[mx];
    vector<pair<int, int>> d[nx];
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> pq;
    vector<int> in;
    pair<int, int> da, db;

    void sendtop()
    {
        if (cnt>n) return;
        while (!pq.empty()&&vs[pq.top().second]) pq.pop();
        if (pq.empty()) for (int i=0; i<sz[cnt]+11; i++) SendB(1);
        else
        {
            auto [w, u]=pq.top();
            for (int i=0; i<sz[cnt]; i++) SendB(w&(1<<i));
            for (int i=0; i<11; i++) SendB(u&(1<<i));
        }
    }
} 

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    n=N;
    for (int i=1; i<N; i++) mn[i]=inf;
    for (int i=0; i<B; i++) d[S[i]].push_back({T[i], D[i]}), d[T[i]].push_back({S[i], D[i]});
    pq.push({0, 0});
    cnt=1;
    for (int i=1; i<=n; i++) sz[i]=ceil(log2(500*i));
    sendtop();
}

void ReceiveB(bool y) {
    in.push_back(y);
    //cout<<"debug "<<sz[cnt]<<' '<<cnt<<'\n';
    if (cnt>n||in.size()<11+sz[cnt]) return;
    da={0, 0};
    for (int i=0; i<sz[cnt]; i++) da.first|=(in[i]<<i);
    for (int i=0; i<11; i++) da.second|=(in[sz[cnt]+i]<<i);
    in.clear();
    db=pq.empty()?make_pair(INT_MAX, INT_MAX):pq.top();
    auto [w, u]=min(da, db);
    if (u>=n) return;
    mn[u]=w;
    vs[u]=1;
    for (auto [v, cw]:d[u]) if (!vs[v]&&w+cw<mn[v]) mn[v]=w+cw, pq.push({w+cw, v});
    cnt++;
    sendtop();
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 38 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16