Submission #1189131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189131		onbert	Two Transportations (JOI19_transportations)	C++20	100 / 100	397 ms	81256 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

namespace {

const int maxn = 2005, INF = 1e10;
int n, m, remain;
vector<pair<int, int>> adj[maxn];
int dist[maxn];
int mx;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

int lg(int x) {
    if (x == 0) return 0;
    else return log2(x);
}

void sendid(int id) {
    // cout << "Asendid " << id << endl;
    int val = -1;
    for (int i=0;i<=id;i++) val += (dist[i] == INF);
    // cout << val << endl;
    int sz = lg(remain-1) + 1;
    for (int i=0;i<sz;i++) {
        SendA(val & (1<<i));
        // cout << (bool)(val & (1<<i));
    }
    // cout << endl;
}
void sendval(int val) {
    // cout << "Asendval " << val << endl;
    for (int i=0;i<9;i++) {
        SendA((val-mx) & (1<<i));
        // cout << (bool)((val-mx) & (1<<i));
    }
    // cout << endl;
}

void firm(int u, int d) {
    // cout << "Afirm " << u << " " << d << endl;
    dist[u] = d;
    mx = max(d, mx);
    for (auto [v, w]:adj[u]) if (dist[v] == INF) pq.push({d + w, v});
    remain--;
    // cout << remain << endl;
}

void takemine(int u, int d, bool needsend) {
    // cout << "Atakemine " << u << " " << d << endl;
    SendA(0);
    sendid(u);
    if (needsend) sendval(d);
    firm(u, d);
    while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
    int ask = 501 + mx;
    if (pq.size() > 0) ask = pq.top().first;
    sendval(ask);
}

int charsleft;
vector<bool> vec;

int fixid(int id) {
    int cnt = -1;
    for (int i=0;i<n;i++) {
        cnt += (dist[i] == INF);
        if (cnt == id) return i;
    }
    return 69420;
}

int nxtfirmval;
void received() {
    int sz = lg(remain-1) + 1;
    int u = 0;
    for (int i=0;i<sz;i++) u += vec[i] * (1<<i);
    u = fixid(u);
    int firmval, ask;
    if (nxtfirmval == -1) {
        firmval = mx;
        for (int i=0;i<9;i++) firmval += vec[i + sz] * (1<<i);
        firm(u, firmval);
        if (remain == 0) return;
        ask = mx;
        for (int i=0;i<9;i++) ask += vec[i + sz + 9] * (1<<i);
    } else {
        firmval = nxtfirmval;
        firm(u, firmval);
        if (remain == 0) return;
        ask = mx;
        for (int i=0;i<9;i++) ask += vec[i + sz] * (1<<i);
        nxtfirmval = -1;
    }
    // cout << "Areceived " << u << " " << firmval << " " << ask << endl;

    while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
    if (pq.size() > 0 && pq.top().first < ask) {
        u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        takemine(u, d, 1);
    } else {
        SendA(1);
        nxtfirmval = ask;
    }

    vec.clear();
}

}  // namespace

void InitA(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V,
           vector<int32_t> W) {
    n = N, m = M, mx = 0;
    remain = n;
    charsleft = 0;
    nxtfirmval = -1;
    vec.clear();
    while (pq.size()) pq.pop();
    for (int i=0;i<n;i++) adj[i].clear();
    for (int i=0;i<n;i++) dist[i] = INF;

    for (int i=0;i<m;i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    takemine(0, 0, 1);
}

void ReceiveA(bool x) {
    // cout << 'A' << x << "\n";
    if (charsleft) {
        vec.push_back(x);
        charsleft--;
        if (!charsleft) {
            received();
        }
        return;
    }
    if (x == 0) {
        charsleft = lg(remain-1) + 1 + 9 + 9;
        if (nxtfirmval != -1) charsleft -= 9;
        return;
    }
    //take
    int u = pq.top().second, d = pq.top().first;
    pq.pop();
    takemine(u, d, 0);
}

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

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

namespace {

const int maxn = 2005, INF = 1e10;
int n, m, remain;
vector<pair<int, int>> adj[maxn];
int dist[maxn];
int mx;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

int lg(int x) {
    if (x == 0) return 0;
    else return log2(x);
}

void firm(int u, int d) {
    // cout << "Bfirm " << u << " " << d << endl;
    dist[u] = d;
    mx = max(d, mx);
    for (auto [v, w]:adj[u]) if (dist[v] == INF) pq.push({d + w, v});
    remain--;
    // cout << remain << endl;
}

void sendid(int id) {
    // cout << "Bsendid " << id << endl;
    int val = -1;
    for (int i=0;i<=id;i++) val += (dist[i] == INF);
    int sz = lg(remain-1) + 1;
    for (int i=0;i<sz;i++) SendB(val & (1<<i));
}
void sendval(int val) {
    // cout << "Bsendval " << val << endl;
    for (int i=0;i<9;i++) SendB((val-mx) & (1<<i));
}

void takemine(int u, int d, bool needsend) {
    SendB(0);
    sendid(u);
    if (needsend) sendval(d);
    firm(u, d);
    while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
    int ask = 501 + mx;
    if (pq.size() > 0) ask = pq.top().first;
    sendval(ask);
}

int charsleft;
vector<bool> vec;

int fixid(int id) {
    int cnt = -1;
    for (int i=0;i<n;i++) {
        cnt += (dist[i] == INF);
        if (cnt == id) return i;
    }
    return 69420;
}

int nxtfirmval;
void received() {
    // for (bool i:vec) cout << i; cout << endl;
    int sz = lg(remain-1) + 1;
    int u = 0;
    for (int i=0;i<sz;i++) u += vec[i] * (1<<i);
    u = fixid(u);
    int firmval, ask;
    if (nxtfirmval == -1) {
        firmval = mx;
        for (int i=0;i<9;i++) firmval += vec[i + sz] * (1<<i);
        firm(u, firmval);
        if (remain == 0) return;
        ask = mx;
        for (int i=0;i<9;i++) ask += vec[i + sz + 9] * (1<<i);
    } else {
        firmval = nxtfirmval;
        firm(u, firmval);
        if (remain == 0) return;
        ask = mx;
        for (int i=0;i<9;i++) ask += vec[i + sz] * (1<<i);
        nxtfirmval = -1;
    }
    // cout << "Brecieved " << u << " " << firmval << " " << ask << endl;

    // cout << ask << endl;
    while (pq.size() > 0 && dist[pq.top().second] != INF) pq.pop();
    if (pq.size() > 0 && pq.top().first < ask) {
        u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        takemine(u, d, 1);
    } else {
        SendB(1);
        nxtfirmval = ask;
    }

    vec.clear();
}

}  // namespace

void InitB(int32_t N, int32_t M, vector<int32_t> U, vector<int32_t> V,
           vector<int32_t> W) {
    n = N, m = M, mx = 0;
    remain = n;
    charsleft = 0;
    nxtfirmval = -1;
    vec.clear();
    while (pq.size()) pq.pop();
    for (int i=0;i<n;i++) dist[i] = INF;
    for (int i=0;i<n;i++) adj[i].clear();

    for (int i=0;i<m;i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
}

void ReceiveB(bool x) {
    // cout << 'B' << x << " " << charsleft << "\n";
    if (charsleft) {
        vec.push_back(x);
        charsleft--;
        if (!charsleft) {
            received();
        }
        return;
    }
    if (x == 0) {
        charsleft = lg(remain-1) + 1 + 9 + 9;
        if (nxtfirmval != -1) charsleft -= 9;
        return;
    }
    //take
    int u = pq.top().second, d = pq.top().first;
    pq.pop();
    takemine(u, d, 0);
}

• 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