Submission #583437

#	Time	Username	Problem	Language	Result	Execution time	Memory
583437		lcj	Two Transportations (JOI19_transportations)	C++17	100 / 100	685 ms	77972 KiB

Azer

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int n, a;
vector<vector<pll>> neighbours;
vector<int> dist;
vector<bool> vis;
priority_queue<pll, vector<pll>, greater<pll>> pq;
int cmaxdist = 0;
default_random_engine generator;

void step();

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
    n = N;a = A;
    neighbours.assign(n, {});
    for (int i = 0; i < a; i++)
    {
        neighbours[U[i]].push_back({V[i], C[i]});
        neighbours[V[i]].push_back({U[i], C[i]});
    }
    generator.seed(42);
    dist.assign(n, 1e9);
    vis.assign(n, 0);
    dist[0] = 0;
    pq.push({0, 0});
    step();
}
int buf = 0;
int cnt = 0;
int target = 0;

int tempd = 0;
int tempn = 0;

void sendNum(int num, int k) {
    //cout << "A > " << num << endl;
    assert(num < (1<<k));
    for (int i = 0; i < k; i++)
    {
        SendA(num & (1 << i));
    }
}

bool rstate = 0;
void step() {
    uniform_int_distribution<int> distr(0, 1);
    rstate = distr(generator);

    while (!pq.empty() && (dist[pq.top().second] < pq.top().first || vis[pq.top().second]))
    {
        pq.pop();
    }
    //cout << "Atop " << pq.top().second << " " << pq.top().first<<endl;
    if (rstate) {
        sendNum(pq.empty() ? 501 : pq.top().first-cmaxdist, 9);
        target = 1;
    }
    else {
        target = 9;
    }
}

void visnode(pll cur) {
    //cout << "Visiting " << cur.second << endl;
    vis[cur.second] = 1;
    cmaxdist = max(cmaxdist, (int)cur.first);
    dist[cur.second] = cur.first;
    for (auto nn : neighbours[cur.second]) {
        if (dist[nn.first] > cur.first+nn.second) {
            dist[nn.first] = cur.first+nn.second;
            pq.push({dist[nn.first], nn.first});
        }
    }
}

void onexit() {
    //cout << "exit" << endl;
    if (!rstate) {
        sendNum(1, 1);
    }
}

void ReceiveA(bool x) {
    buf += x*(1 << cnt);
    cnt++;
    if (cnt==target) {
        cnt = 0;
        int buffer = buf;
        buf = 0;
        if (target == 9) {
            if (rstate) {
                int trudist = buffer+cmaxdist;
                pll cur = {trudist, tempn};
                visnode(cur);
                step();
            }
            else {
                tempd = buffer+cmaxdist;
                int own = pq.empty() ? 501 : pq.top().first-cmaxdist;
                if (own == 501 && buffer == 501) {
                    onexit();
                    return;
                }
                if (buffer <= own) {
                    sendNum(1, 1);
                    target = 11;
                }
                else {
                    sendNum(0, 1);
                    auto cur = pq.top();
                    sendNum(cur.second, 11);
                    sendNum(own, 9);
                    pq.pop();
                    visnode(cur);
                    step();
                }
            }
        }
        else if (target == 11) {
            if (rstate) {
                tempn = buffer;
                target = 9;
            }
            else {
                pll cur = {tempd, buffer};
                visnode(cur);
                step();
            }
        }
        else {
            if (buffer) { //Own is better
                if (pq.empty()) {
                    onexit();
                    return;
                }
                const auto cur = pq.top();
                pq.pop();
                visnode(cur);
                sendNum(cur.second, 11);
                step();
            }
            else { //Other is better
                target = 11;
            }
        }
    }
}

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

Baijan

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

namespace name
{
    int n, a;
vector<vector<pll>> neighbours;
vector<int> dist;
vector<bool> vis;
priority_queue<pll, vector<pll>, greater<pll>> pq;
int cmaxdist = 0;
default_random_engine generator;

void step();

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
    n = N;a = B;
    neighbours.assign(n, {});
    for (int i = 0; i < a; i++)
    {
        neighbours[S[i]].push_back({T[i], D[i]});
        neighbours[T[i]].push_back({S[i], D[i]});
    }
    generator.seed(42);
    dist.assign(n, 1e9);
    vis.assign(n, 0);
    dist[0] = 0;
    pq.push({0, 0});
    step();
}
int buf = 0;
int cnt = 0;
int target = 0;

int tempd = 0;
int tempn = 0;

void sendNum(int num, int k) {
    //cout << "B > " << num << endl;
    assert(num < (1<<k));
    for (int i = 0; i < k; i++)
    {
        SendB(num & (1 << i));
    }
}

bool rstate = 0;
void step() {
    uniform_int_distribution<int> distr(0, 1);
    rstate = !distr(generator);

    while (!pq.empty() && (dist[pq.top().second] < pq.top().first || vis[pq.top().second]))
    {
        pq.pop();
    }
    //cout << "Btop " << pq.top().second << " " << pq.top().first<<endl;
    if (rstate) {
        sendNum(pq.empty() ? 501 : pq.top().first-cmaxdist, 9);
        target = 1;
    }
    else {
        target = 9;
    }
}

void visnode(pll cur) {
    //cout << "Visiting " << cur.second << endl;
    vis[cur.second] = 1;
    cmaxdist = max(cmaxdist, (int)cur.first);
    dist[cur.second] = cur.first;
    for (auto nn : neighbours[cur.second]) {
        if (dist[nn.first] > cur.first+nn.second) {
            dist[nn.first] = cur.first+nn.second;
            pq.push({dist[nn.first], nn.first});
        }
    }
}

void onexit() {
    //cout << "exit" << endl;
    if (!rstate) {
        sendNum(1, 1);
    }
}

void ReceiveB(bool x) {
    buf += x*(1 << cnt);
    cnt++;
    if (cnt==target) {
        cnt = 0;
        int buffer = buf;
        buf = 0;
        if (target == 9) {
            if (rstate) {
                int trudist = buffer+cmaxdist;
                pll cur = {trudist, tempn};
                visnode(cur);
                step();
            }
            else {
                tempd = buffer+cmaxdist;
                int own = pq.empty() ? 501 : pq.top().first-cmaxdist;
                if (own == 501 && buffer == 501) {
                    onexit();
                    return;
                }
                if (buffer <= own) {
                    sendNum(1, 1);
                    target = 11;
                }
                else {
                    sendNum(0, 1);
                    auto cur = pq.top();
                    sendNum(cur.second, 11);
                    sendNum(own, 9);
                    pq.pop();
                    visnode(cur);
                    step();
                }
            }
        }
        else if (target == 11) {
            if (rstate) {
                tempn = buffer;
                target = 9;
            }
            else {
                pll cur = {tempd, buffer};
                visnode(cur);
                step();
            }
        }
        else {
            if (buffer) { //Own is better
                if (pq.empty()) {
                    onexit();
                    return;
                }
                const auto cur = pq.top();
                pq.pop();
                visnode(cur);
                sendNum(cur.second, 11);
                step();
            }
            else { //Other is better
                target = 11;
            }
        }
    }
}
} 

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

void ReceiveB(bool x) {
    name::ReceiveB(x);
}

• 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