Submission #708364

#	Time	Username	Problem	Language	Result	Execution time	Memory
708364		LittleCube	Two Transportations (JOI19_transportations)	C++14	100 / 100	912 ms	48852 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
    int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
    int phase; // 1: receive distance, 2: receive node
    bool vis[2000] = {};
    vector<pii> E[2000];
    vector<int> receive;

    priority_queue<pii, vector<pii>, greater<pii>> pq;

    void send(int message, int bit)
    {
        for (int i = bit - 1; i >= 0; i--)
            SendA((message >> i) & 1);
    }

    void calcNext()
    {
        cerr << "calcNextA " << u << ' ' << ld << '\n';
        T--;
        vis[u] = 1;
        d[u] = ld;
        for (auto [v, w] : E[u])
            if (d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                pq.push(pii(d[v], v));
            }
        if (T)
        {
            while (!pq.empty() && vis[pq.top().S])
                pq.pop();
            if (!pq.empty())
                u = pq.top().S, dA = d[u] - ld, dB = 0;
            else
                u = 0, dA = 511, dB = 0;
            send(dA, 9);
            phase = 1;
        }
    }

    void check_distance()
    {
        for (int b = 0; b < 9; b++)
            dB = dB * 2 + receive[b];
        receive.clear();
        if (dB < dA)
            phase = 2;
        else
        {
            send(u, 11);
            ld += dA;
            calcNext();
        }
    }

    void update_distance()
    {
        u = 0;
        ld += dB;
        for (int b = 0; b < 11; b++)
            u = u * 2 + receive[b];
        receive.clear();
        calcNext();
    }

}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C)
{
    ::N = N;
    ::T = N;
    for (int i = 1; i < N; i++)
        d[i] = 1'000'000'000;
    for (int i = 0; i < A; i++)
    {
        E[U[i]].emplace_back(pii(V[i], C[i]));
        E[V[i]].emplace_back(pii(U[i], C[i]));
    }
    calcNext();
}

void ReceiveA(bool x)
{
    receive.emplace_back(x);
    if (receive.size() == 9 && phase == 1)
        check_distance();
    if (receive.size() == 11 && phase == 2)
        update_distance();
}

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

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

namespace
{
    int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
    int phase; // 1: receive distance, 2: receive node
    bool vis[2000] = {};
    vector<pii> E[2000];
    vector<int> receive;

    priority_queue<pii, vector<pii>, greater<pii>> pq;

    void send(int message, int bit)
    {
        for (int i = bit - 1; i >= 0; i--)
            SendB((message >> i) & 1);
    }

    void calcNext()
    {
        cerr << "calcNextB " << u << ' ' << ld << '\n';
        T--;
        vis[u] = 1;
        d[u] = ld;
        for (auto [v, w] : E[u])
            if (d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                pq.push(pii(d[v], v));
            }
        if (T)
        {
            while (!pq.empty() && vis[pq.top().S])
                pq.pop();
            if (!pq.empty())
                u = pq.top().S, dA = 0, dB = d[u] - ld;
            else
                u = 0, dA = 0, dB = 511;
            send(dB, 9);
            phase = 1;
        }
    }

    void check_distance()
    {
        for (int b = 0; b < 9; b++)
            dA = dA * 2 + receive[b];
        receive.clear();
        if (dA <= dB)
            phase = 2;
        else
        {
            send(u, 11);
            ld += dB;
            calcNext();
        }
    }

    void update_distance()
    {
        u = 0;
        ld += dA;
        for (int b = 0; b < 11; b++)
            u = u * 2 + receive[b];
        receive.clear();
        calcNext();
    }
}

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D)
{
    ::N = N;
    ::T = N;
    for (int i = 1; i < N; i++)
        d[i] = 1'000'000'000;
    for (int i = 0; i < B; i++)
    {
        E[S[i]].emplace_back(pii(T[i], D[i]));
        E[T[i]].emplace_back(pii(S[i], D[i]));
    }
    calcNext();
}

void ReceiveB(bool y)
{
    receive.emplace_back(y);
    if (receive.size() == 9 && phase == 1)
        check_distance();
    if (receive.size() == 11 && phase == 2)
        update_distance();
}

Compilation message (stderr)

Azer.cpp: In function 'void {anonymous}::calcNext()':
Azer.cpp:30:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         for (auto [v, w] : E[u])
      |                   ^
Azer.cpp: At global scope:
Azer.cpp:10:26: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
   10 |     int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
      |                          ^~~

Baijan.cpp: In function 'void {anonymous}::calcNext()':
Baijan.cpp:30:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         for (auto [v, w] : E[u])
      |                   ^
Baijan.cpp: At global scope:
Baijan.cpp:10:26: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
   10 |     int N, d[2000] = {}, cnt = 0, ld = 0, u = 0, T, dA, dB;
      |                          ^~~

• 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