Submission #1189347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189347		12345678	Two Transportations (JOI19_transportations)	C++20	100 / 100	288 ms	49084 KiB

Azer

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

using namespace std;

namespace {
    const int nx=2e3+5, inf=1e9, kx=9;

    mt19937 rng(12345678);

    enum MODE {WAIT, SENDER_FIRST, SENDER_WAIT, SENDER_SECOND, RECIEVER_FIRST, RECIEVER_SECOND};
    MODE mode;

    int n, cur, mn[nx], vs[nx], mx, w, u, randm[nx], saved;
    vector<pair<int, int>> d[nx];
    vector<int> in;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    void sendtop()
    {
        while (!pq.empty()&&vs[pq.top().second]) pq.pop();
        //cout<<"send top "<<pq.top().first<<' '<<pq.top().second<<'\n';
        if (pq.empty()) for (int i=0; i<kx; i++) SendA(1);
        else
        {
            auto [w, u]=pq.top();
            for (int i=0; i<kx; i++) SendA((w-mx)&(1<<i));
        }
    }

    void sendnum()
    {
        for (int i=0; i<11; i++) SendA(pq.top().second&(1<<i));
    }

    void update(int w, int u)
    {
        //cout<<"update A "<<w<<' '<<u<<'\n';
        cur++;
        mn[u]=mx=w, vs[u]=1;
        for (auto [v, cw]:d[u]) if (mn[v]>w+cw) mn[v]=w+cw, pq.push({mn[v], v});
    }
} 

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n=N;
    cur=1;
    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]});
    for (int i=1; i<=N; i++) randm[i]=rng()%2; //cout<<"randm A "<<randm[i]<<'\n';
    pq.push({0, 0});
    mode=WAIT;
    if (randm[cur]) SendA(1);
}

void ReceiveA(bool x) {
    //cout<<"mode a "<<mode<<' '<<x<<'\n';
    if (mode==WAIT)
    {
        if (x==1) SendA(0), mode=SENDER_FIRST, ReceiveA(0);
        else mode=RECIEVER_FIRST;
    }
    else if (mode==SENDER_FIRST)
    {
        sendtop();
        mode=SENDER_WAIT;
    }
    else if (mode==SENDER_WAIT)
    {
        if (x==1) mode=SENDER_SECOND;
        else
        {
            update(pq.top().first, pq.top().second);
            sendnum();
            if (cur>n) return;
            mode=WAIT;
            if (randm[cur]) SendA(1);
        }
    }
    else if (mode==SENDER_SECOND)
    {
        in.push_back(x);
        if (in.size()<20) return;
        u=0, w=0;
        for (int i=0; i<11; i++) u|=in[i]<<i;
        for (int i=0; i<kx; i++) w|=in[i+11]<<i;
        in.clear();
        w=mx+w;
        update(w, u);
        if (cur>n) return;
        mode=WAIT;
        if (randm[cur]) SendA(1);
    }
    else if (mode==RECIEVER_FIRST)
    {
        in.push_back(x);
        if (in.size()<kx) return;
        w=0;
        for (int i=0; i<kx; i++) w|=(in[i]<<i);
        w=mx+w;
        in.clear();
        while (!pq.empty()&&vs[pq.top().second]) pq.pop();
        int cw=INT_MAX;
        if (!pq.empty()) cw=pq.top().first;
        if (w<=cw)
        {
            SendA(0);
            saved=w;
            mode=RECIEVER_SECOND;
        }
        else
        {
            SendA(1);
            sendnum();
            sendtop();
            update(pq.top().first, pq.top().second);
            if (cur>n) return;
            mode=WAIT;
            if (randm[cur]) SendA(1);
        }
    }
    else if (mode==RECIEVER_SECOND)
    {
        in.push_back(x);
        if (in.size()<11) return;
        u=0;
        for (int i=0; i<11; i++) u|=(in[i]<<i);
        in.clear();
        update(saved, u);
        if (cur>n) return;
        mode=WAIT;
        if (randm[cur]) SendA(1);
    }
}

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, kx=9;

    mt19937 rng(12345678);

    enum MODE {WAIT, SENDER_FIRST, SENDER_WAIT, SENDER_SECOND, RECIEVER_FIRST, RECIEVER_SECOND};
    MODE mode;

    int n, cur, mn[nx], vs[nx], mx, w, u, randm[nx], saved;
    vector<pair<int, int>> d[nx];
    vector<int> in;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    void sendtop()
    {
        while (!pq.empty()&&vs[pq.top().second]) pq.pop();
        if (pq.empty()) for (int i=0; i<kx; i++) SendB(1);
        else
        {
            auto [w, u]=pq.top();
            for (int i=0; i<kx; i++) SendB((w-mx)&(1<<i));
        }
    }

    void sendnum()
    {
        for (int i=0; i<11; i++) SendB(pq.top().second&(1<<i));
    }

    void update(int w, int u)
    {
        //cout<<"update B "<<w<<' '<<u<<'\n';
        cur++;
        mn[u]=mx=w, vs[u]=1;
        for (auto [v, cw]:d[u]) if (mn[v]>w+cw) mn[v]=w+cw, pq.push({mn[v], v});
    }
} 

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    n=N;
    cur=1;
    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]});
    for (int i=1; i<=N; i++) randm[i]=!(rng()%2); //cout<<"randm B "<<randm[i]<<'\n';
    pq.push({0, 0});
    mode=WAIT;
    if (randm[cur]) SendB(1);
}

void ReceiveB(bool y) {
    //cout<<"mode b "<<mode<<' '<<y<<'\n';
    if (mode==WAIT)
    {
        if (y==1) SendB(0), mode=SENDER_FIRST, ReceiveB(0);
        else mode=RECIEVER_FIRST;
    }
    else if (mode==SENDER_FIRST)
    {
        sendtop();
        mode=SENDER_WAIT;
    }
    else if (mode==SENDER_WAIT)
    {
        if (y==1) mode=SENDER_SECOND;
        else
        {
            update(pq.top().first, pq.top().second);
            sendnum();
            if (cur>n) return;
            mode=WAIT;
            if (randm[cur]) SendB(1);
        }
    }
    else if (mode==SENDER_SECOND)
    {
        in.push_back(y);
        if (in.size()<20) return;
        u=0, w=0;
        for (int i=0; i<11; i++) u|=in[i]<<i;
        for (int i=0; i<kx; i++) w|=in[i+11]<<i;
        in.clear();
        w=mx+w;
        update(w, u);
        if (cur>n) return;
        mode=WAIT;
        if (randm[cur]) SendB(1);
    }
    else if (mode==RECIEVER_FIRST)
    {
        in.push_back(y);
        if (in.size()<kx) return;
        w=0;
        for (int i=0; i<kx; i++) w|=(in[i]<<i);
        w=mx+w;
        in.clear();
        while (!pq.empty()&&vs[pq.top().second]) pq.pop();
        int cw=INT_MAX;
        if (!pq.empty()) cw=pq.top().first;
        if (w<=cw)
        {
            SendB(0);
            saved=w;
            mode=RECIEVER_SECOND;
        }
        else
        {
            SendB(1);
            sendnum();
            sendtop();
            update(pq.top().first, pq.top().second);
            if (cur>n) return;
            mode=WAIT;
            if (randm[cur]) SendB(1);
        }
    }
    else if (mode==RECIEVER_SECOND)
    {
        in.push_back(y);
        if (in.size()<11) return;
        u=0;
        for (int i=0; i<11; i++) u|=(in[i]<<i);
        in.clear();
        update(saved, u);
        if (cur>n) return;
        mode=WAIT;
        if (randm[cur]) SendB(1);
    }
}

• 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