Submission #1222598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222598		Triseedot	Two Transportations (JOI19_transportations)	C++20	0 / 100	3079 ms	35916 KiB

Azer

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

namespace {
using namespace std;

template <typename T>
using min_heap = priority_queue<T, vector<T>, less<T>>;
#define bit(n, i) (((n) >> (i)) & 1)
mt19937 rng(42);
int n;
vector<vector<pair<int, int>>> g;
int last = 0;
vector<bool> b;
vector<int> dist;
set<pair<int, int>> pq;
int state, ptr, curr;
int delta, delta_v;

const int X = 0;

void recalc(int v) {
    for (auto [u, w] : g[v]) {
        if (dist[u] == -1 || dist[u] > dist[v] + w) {
            auto it = pq.find({dist[u], u});
            if (it != pq.end()) {
                pq.erase(it);
            }
            dist[u] = dist[v] + w;
            pq.insert({dist[u], u});
        }
    }
}

void process() {
    int delta1 = 0;
    if (pq.empty()) {
        delta1 = 501;
    }
    else {
        auto [dist_v, v] = *pq.begin();
        delta1 = dist_v - last;
    }
    for (int i = 0; i < 9; i++) {
        SendA(bit(delta1, i));
    }
    state = 1;
    ptr = 0;
    delta = 0;
    delta_v = 0;
}
}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n = N;
    g.resize(n);
    for (int i = 0; i < A; i++) {
        g[U[i]].push_back({V[i], C[i]});
        g[V[i]].push_back({U[i], C[i]});
    }

    dist.assign(n, -1);
    dist[0] = 0;
    b.resize(n);
    for (int i = 0; i < n; i++) {
        b[i] = rng() % 2;
    }

    recalc(0);
    curr = 1;

    if (b[curr] == X) {
        process();
    }
    else {
        state = 0;
        delta = 0;
        ptr = 0;
    }
}

void ReceiveA(bool x) {
    if (state == 0) {
        if (x) {
            delta += 1 << ptr;
        }
        ptr++;
        if (ptr == 9) {
            int delta1 = 0, v;
            if (pq.empty()) {
                delta1 = 501;
                v = 0;
            }
            else {
                auto [dist_v, v1] = *pq.begin();
                delta1 = dist_v - last;
                v = v1;
            }
            if (delta1 < delta) {
                SendA(true);
                for (int i = 0; i < 9; i++) {
                    SendA(bit(delta1, i));
                }
                for (int i = 0; i < 11; i++) {
                    SendA(bit(v, i));
                }
                recalc(v);
                pq.erase({dist[v], v});
                last = dist[v];
                curr++;
                if (curr == n) {

                }
                else if (b[curr] == X) {
                    process();
                }
                else {
                    state = 0;
                    delta = 0;
                    ptr = 0;
                }
            }
            else {
                SendA(false);
                state = 2;
                delta_v = 0;
                ptr = 0;
            }
        }
    }
    else if (state == 1) {
        if (ptr == 0) {
            if (x == 0) {
                auto [dist_v, v] = *pq.begin();
                recalc(v);
                pq.erase(pq.begin());
                for (int i = 0; i < 11; i++) {
                    SendA(bit(v, i));
                }
                last = dist[v];
                curr++;
                if (curr == n) {

                }
                else if (b[curr] == X) {
                    process();
                }
                else {
                    state = 0;
                    delta = 0;
                    ptr = 0;
                }
            }
            else {
                ptr++;
            }
        }
        else if (ptr <= 9) {
            if (x == 1) {
                delta += 1 << (ptr - 1);
            }
            ptr++;
        }
        else if (ptr <= 20) {
            if (x == 1) {
                delta_v += 1 << (ptr - 10);
            }
            ptr++;
            if (ptr == 21) {
                int v = delta_v;
                auto it = pq.find({dist[v], v});
                if (it != pq.end()) {
                    pq.erase(it);
                }
                dist[v] = last + delta;
                recalc(v);
                last = dist[v];
                curr++;
                if (curr == n) {

                }
                else if (b[curr] == X) {
                    process();
                }
                else {
                    state = 0;
                    delta = 0;
                    ptr = 0;
                }
            }
        }
    }
    else {
        if (x) {
            delta_v += 1 << ptr;
        }
        ptr++;
        if (ptr == 11) {
            int v = delta_v;
            auto it = pq.find({dist[v], v});
            if (it != pq.end()) {
                pq.erase(it);
            }
            dist[v] = last + delta;
            recalc(v);
            last = dist[v];
            curr++;
            if (curr == n) {

            }
            else if (b[curr] == X) {
                process();
            }
            else {
                state = 0;
                delta = 0;
                ptr = 0;
            }
        }
    }
}

vector<int> Answer() {
    return dist;
}

Baijan

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

namespace {
    using namespace std;

    template <typename T>
    using min_heap = priority_queue<T, vector<T>, less<T>>;
#define bit(n, i) (((n) >> (i)) & 1)
    mt19937 rng(42);
    int n;
    vector<vector<pair<int, int>>> g;
    int last = 0;
    vector<bool> b;
    vector<int> dist;
    set<pair<int, int>> pq;
    int state, ptr, curr;
    int delta, delta_v;

    const int X = 1;

    void recalc(int v) {
        for (auto [u, w] : g[v]) {
            if (dist[u] == -1 || dist[u] > dist[v] + w) {
                auto it = pq.find({dist[u], u});
                if (it != pq.end()) {
                    pq.erase(it);
                }
                dist[u] = dist[v] + w;
                pq.insert({dist[u], u});
            }
        }
    }

    void process() {
        int delta1 = 0;
        if (pq.empty()) {
            delta1 = 501;
        }
        else {
            auto [dist_v, v] = *pq.begin();
            delta1 = dist_v - last;
        }
        for (int i = 0; i < 9; i++) {
            SendB(bit(delta1, i));
        }
        state = 1;
        ptr = 0;
        delta = 0;
        delta_v = 0;
    }
}

void InitB(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n = N;
    g.resize(n);
    for (int i = 0; i < A; i++) {
        g[U[i]].push_back({V[i], C[i]});
        g[V[i]].push_back({U[i], C[i]});
    }

    dist.assign(n, -1);
    dist[0] = 0;
    b.resize(n);
    for (int i = 0; i < n; i++) {
        b[i] = rng() % 2;
    }

    recalc(0);
    curr = 1;

    if (b[curr] == X) {
        process();
    }
    else {
        state = 0;
        delta = 0;
        ptr = 0;
    }
}

void ReceiveB(bool x) {
    if (state == 0) {
        if (x) {
            delta += 1 << ptr;
        }
        ptr++;
        if (ptr == 9) {
            int delta1 = 0, v;
            if (pq.empty()) {
                delta1 = 501;
                v = 0;
            }
            else {
                auto [dist_v, v1] = *pq.begin();
                delta1 = dist_v - last;
                v = v1;
            }
            if (delta1 < delta) {
                SendB(true);
                for (int i = 0; i < 9; i++) {
                    SendB(bit(delta1, i));
                }
                for (int i = 0; i < 11; i++) {
                    SendB(bit(v, i));
                }
                recalc(v);
                pq.erase({dist[v], v});
                last = dist[v];
                curr++;
                if (curr == n) {

                }
                else if (b[curr] == X) {
                    process();
                }
                else {
                    state = 0;
                    delta = 0;
                    ptr = 0;
                }
            }
            else {
                SendB(false);
                state = 2;
                delta_v = 0;
                ptr = 0;
            }
        }
    }
    else if (state == 1) {
        if (ptr == 0) {
            if (x == 0) {
                auto [dist_v, v] = *pq.begin();
                recalc(v);
                pq.erase(pq.begin());
                for (int i = 0; i < 11; i++) {
                    SendB(bit(v, i));
                }
                last = dist[v];
                curr++;
                if (curr == n) {

                }
                else if (b[curr] == X) {
                    process();
                }
                else {
                    state = 0;
                    delta = 0;
                    ptr = 0;
                }
            }
            else {
                ptr++;
            }
        }
        else if (ptr <= 9) {
            if (x == 1) {
                delta += 1 << (ptr - 1);
            }
            ptr++;
        }
        else if (ptr <= 20) {
            if (x == 1) {
                delta_v += 1 << (ptr - 10);
            }
            ptr++;
            if (ptr == 21) {
                int v = delta_v;
                auto it = pq.find({dist[v], v});
                if (it != pq.end()) {
                    pq.erase(it);
                }
                dist[v] = last + delta;
                recalc(v);
                last = dist[v];
                curr++;
                if (curr == n) {

                }
                else if (b[curr] == X) {
                    process();
                }
                else {
                    state = 0;
                    delta = 0;
                    ptr = 0;
                }
            }
        }
    }
    else {
        if (x) {
            delta_v += 1 << ptr;
        }
        ptr++;
        if (ptr == 11) {
            int v = delta_v;
            auto it = pq.find({dist[v], v});
            if (it != pq.end()) {
                pq.erase(it);
            }
            dist[v] = last + delta;
            recalc(v);
            last = dist[v];
            curr++;
            if (curr == n) {

            }
            else if (b[curr] == X) {
                process();
            }
            else {
                state = 0;
                delta = 0;
                ptr = 0;
            }
        }
    }
}

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