제출 #1126236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126236		OI_Account	Two Transportations (JOI19_transportations)	C++20	52 / 100	367 ms	55740 KiB

Azer

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

namespace {

    typedef long long ll;

    const int N = 2000;
    const int INF = 1'000'100;
    const int M = 20;

    int n, m, mark[N + 10], ans[N + 10];
    vector<pair<int, int>> adj[N + 10];
    set<pair<int, int>> s;
    int dis[N + 10];

    mt19937 rng(123);
    int bl, readDis, lastDist, type;
    vector<int> detail, vecDis;

    void readInput(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
        n = N;
        m = A;
        for (int i = 0; i < m; i++) {
            int u = U[i], v = V[i], c = C[i];
            adj[u].push_back({v, c});
            adj[v].push_back({u, c});
        }
    }

    void checkDis(int u) {
        for (auto [v, w]: adj[u])
            if (dis[u] + w < dis[v]) {
                s.erase({dis[v], v});
                dis[v] = dis[u] + w;
                s.insert({dis[v], v});
            }
    }

    void init() {
        for (int i = 1; i < n; i++) {
            mark[i] = 0;
            dis[i] = INF;
            s.insert({dis[i], i});
        }
        dis[0] = 0;
        mark[0] = true;
        checkDis(0);
    }

    void outputInt(int x, int M) {
        for (int j = M - 1; j >= 0; j--) {
            int bit = ((x & (1 << j))? 1: 0);
            SendA(bit);
        }
    }

    void outputDis(int x) {
        outputInt(x, M);
    }

    void outputVer(int x) {
        outputInt(x, 11);
    }

    void addVer(int u) {
        mark[u] = true;
        s.erase({dis[u], u});
        ans[u] = dis[u];
        checkDis(u);
    }

    bool isA() {
        return rng() % 2 == 0;
    }

    void step() {
        if (!isA()) {
            type = 2;
            readDis = true;
            return;
        }
        bool is = false;
        for (int i = 0; i < n; i++)
            if (mark[i] == false)
                is = true;
        if (!is)
            return;
        type = 1;
        bl = true;
        outputDis(s.begin() -> first);
    }

    void newGood(int u, int dist) {
        s.erase({dis[u], u});
        dis[u] = dist;
        addVer(u);
    }

    int calcDis() {
        int res = 0;
        for (int i = 0; i < 20; i++)
            res = res * 2 + vecDis[i];
        vecDis.clear();
        return res;
    }

    int calcVer() {
        int res = 0;
        for (int i = 0; i < 11; i++)
            res = res * 2 + detail[i];
        detail.clear();
        return res;
    }

    void checkDetail() {
        int dist = 0, u = 0;
        for (int i = 0; i < 20; i++)
            dist = dist * 2 + detail[i];
        for (int i = 20; i < 31; i++)
            u = u * 2 + detail[i];
        detail.clear();
        newGood(u, dist);
    }

    void ReceiveA2(bool x) {
        if (readDis) {
            vecDis.push_back(x);
            if (vecDis.size() == 20) {
                readDis = false;
                int dist = calcDis();
                if (s.begin() -> first < dist) {
                    SendA(1);
                    outputDis(s.begin() -> first);
                    outputVer(s.begin() -> second);
                    addVer(s.begin() -> second);
                    step();
                }
                else {
                    lastDist = dist;
                    SendA(0);
                }
            }
        }
        else {
            detail.push_back(x);
            if (detail.size() == 11) {
                int u = calcVer();
                newGood(u, lastDist);
                step();
            }
        }
    }
} 

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    readInput(N, A, U, V, C);
    init();
    step();
}

void ReceiveA(bool x) {
    if (type == 2) {
        ReceiveA2(x);
        return;
    }
    if (bl) {
        bl = false;
        if (x == 0) {
            outputVer(s.begin() -> second);
            addVer(s.begin() -> second);
            step();
        }
    }
    else {
        detail.push_back(x);
        if (detail.size() == 31) {
            checkDetail();
            step();
        }
    }
}

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

Baijan

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

namespace {

    typedef long long ll;

    const int N = 2000;
    const int INF = 1'000'100;
    const int M = 20;

    int n, m, mark[N + 10], ans[N + 10];
    vector<pair<int, int>> adj[N + 10];
    set<pair<int, int>> s;
    int dis[N + 10];

    mt19937 rng(123);
    int bl, readDis, lastDist, type;
    vector<int> detail, vecDis;

    void readInput(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
        n = N;
        m = A;
        for (int i = 0; i < m; i++) {
            int u = U[i], v = V[i], c = C[i];
            adj[u].push_back({v, c});
            adj[v].push_back({u, c});
        }
    }

    void checkDis(int u) {
        for (auto [v, w]: adj[u])
            if (dis[u] + w < dis[v]) {
                s.erase({dis[v], v});
                dis[v] = dis[u] + w;
                s.insert({dis[v], v});
            }
    }

    void init() {
        for (int i = 1; i < n; i++) {
            dis[i] = INF;
            s.insert({dis[i], i});
            mark[i] = 0;
        }
        dis[0] = 0;
        mark[0] = true;
        checkDis(0);
    }

    void outputInt(int x, int M) {
        for (int j = M - 1; j >= 0; j--) {
            int bit = ((x & (1 << j))? 1: 0);
            SendB(bit);
        }
    }

    void outputDis(int x) {
        outputInt(x, M);
    }

    void outputVer(int x) {
        outputInt(x, 11);
    }

    bool isB() {
        return rng() % 2 == 1;
    }

    void step() {
        if (!isB()) {
            type = 2;
            readDis = true;
            return;
        }
        bool is = false;
        for (int i = 0; i < n; i++)
            if (mark[i] == false)
                is = true;
        if (!is)
            return;
        type = 1;
        bl = true;
        outputDis(s.begin() -> first);
    }

    void addVer(int u) {
        mark[u] = true;
        s.erase({dis[u], u});
        ans[u] = dis[u];
        checkDis(u);
    }

    void newGood(int u, int dist) {
        s.erase({dis[u], u});
        dis[u] = dist;
        addVer(u);
    }

    int calcDis() {
        int res = 0;
        for (int i = 0; i < 20; i++)
            res = res * 2 + vecDis[i];
        vecDis.clear();
        return res;
    }

    int calcVer() {
        int res = 0;
        for (int i = 0; i < 11; i++)
            res = res * 2 + detail[i];
        detail.clear();
        return res;
    }

    void checkDetail() {
        int dist = 0, u = 0;
        for (int i = 0; i < 20; i++)
            dist = dist * 2 + detail[i];
        for (int i = 20; i < 31; i++)
            u = u * 2 + detail[i];
        detail.clear();
        newGood(u, dist);
    }

    void ReceiveB2(bool x) {
        if (readDis) {
            vecDis.push_back(x);
            if (vecDis.size() == 20) {
                readDis = false;
                int dist = calcDis();
                if (s.begin() -> first < dist) {
                    SendB(1);
                    outputDis(s.begin() -> first);
                    outputVer(s.begin() -> second);
                    addVer(s.begin() -> second);
                    step();
                }
                else {
                    lastDist = dist;
                    SendB(0);
                }
            }
        }
        else {
            detail.push_back(x);
            if (detail.size() == 11) {
                int u = calcVer();
                newGood(u, lastDist);
                step();
            }
        }
    }
} 

void InitB(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    readInput(N, A, U, V, C);
    init();
    step();
}

void ReceiveB(bool x) {
    if (type == 2) {
        ReceiveB2(x);
        return;
    }
    if (bl) {
        bl = false;
        if (x == 0) {
            outputVer(s.begin() -> second);
            addVer(s.begin() -> second);
            step();
        }
    }
    else {
        detail.push_back(x);
        if (detail.size() == 31) {
            checkDetail();
            step();
        }
    }
}

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