Submission #1287536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287536		lightentheshadow	Two Transportations (JOI19_transportations)	C++20	100 / 100	345 ms	51708 KiB

Azer

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

int n, m, goalBit, currBit, currNum, cntDone, bestNode = 0, bestDiff;
vector<pair<int, int>> adj[2005];
int dis[2005], currMn = 0;
bool done[2005];

void sendNum(int num, int bit) {
    if (bit == 9 && num > 500) num = 501;
    for (int i = 0; i < bit; i++)
        if (num & (1 << i)) SendA(true);
            else SendA(false);
}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n = N; m = A;
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i], C[i]});
        adj[V[i]].push_back({U[i], C[i]});
    }
    for (int i = 0; i < n; i++)
        dis[i] = 1e9;
    dis[0] = 0;
    sendNum(0, 9); goalBit = 9; currBit = 0; currNum = 0; cntDone = 0;
}

void walk(int u) {
    currMn = dis[u];
    done[u] = true; cntDone++;
    for (auto [v, w]: adj[u])
        dis[v] = min(dis[v], dis[u] + w);
    if (cntDone == n) return ;
    bestNode = n; dis[n] = 1e9;
    for (int i = 0; i < n; i++)
        if (!done[i] && dis[i] < dis[bestNode]) bestNode = i;
    bestDiff = dis[bestNode] - currMn;
    sendNum(bestDiff, 9); goalBit = 9;
}

void ReceiveA(bool quinn) {
    if (quinn) currNum += (1 << currBit);
    currBit++;
    if (currBit != goalBit) return ;

    if (goalBit == 9) {
        if (bestDiff <= currNum) {
            sendNum(bestNode, 11);
            walk(bestNode);
        }
        else {
            bestDiff = currNum;
            goalBit = 11;
        }
    }
    else {
        dis[currNum] = currMn + bestDiff;
        walk(currNum);
    }

    currBit = currNum = 0;
}

vector<int> Answer() {
    vector<int> res;
    for (int i = 0; i < n; i++)
        res.push_back(dis[i]);
    return res;
}

Baijan

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

int n, m, goalBit, currBit, currNum, cntDone, bestNode = 0, bestDiff;
vector<pair<int, int>> adj[2005];
int dis[2005], currMn = 0;
bool done[2005];

void sendNum(int num, int bit) {
    if (bit == 9 && num > 500) num = 501;
    for (int i = 0; i < bit; i++)
        if (num & (1 << i)) SendB(true);
            else SendB(false);
}

void InitB(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n = N; m = A;
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i], C[i]});
        adj[V[i]].push_back({U[i], C[i]});
    }
    for (int i = 0; i < n; i++)
        dis[i] = 1e9;
    dis[0] = 0;
    sendNum(0, 9); goalBit = 9; currBit = 0; currNum = 0; cntDone = 0;
}

void walk(int u) {
    currMn = dis[u];
    done[u] = true; cntDone++;
    for (auto [v, w]: adj[u])
        dis[v] = min(dis[v], dis[u] + w);

    if (cntDone == n) return ;
    bestNode = n; dis[n] = 1e9;
    for (int i = 0; i < n; i++)
        if (!done[i] && dis[i] < dis[bestNode]) bestNode = i;
    bestDiff = dis[bestNode] - currMn;
    sendNum(bestDiff, 9); goalBit = 9;
}

void ReceiveB(bool han) {
    if (han) currNum += (1 << currBit);
    currBit++;
    if (currBit != goalBit) return ;

    if (goalBit == 9) {
        if (bestDiff < currNum) {
            sendNum(bestNode, 11);
            walk(bestNode);
        }
        else {
            bestDiff = currNum;
            goalBit = 11;
        }
    }
    else {
        dis[currNum] = currMn + bestDiff;
        walk(currNum);
    }

    currBit = currNum = 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