Submission #794809

#	Time	Username	Problem	Language	Result	Execution time	Memory
794809		stasio6	Two Transportations (JOI19_transportations)	C++17	100 / 100	770 ms	48648 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define PB push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

namespace {

vector<pii> edges[2002];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1000002], odw[1000002];
int lastdist, mydist, myindx;
int LD = 0;
bool indx;
int poz, pot, val, gl_N;

void encode(int x, int format) {
    if (x > (1<<format)) x = (1<<format) - 3;
    for (int i = 0; i < format; i++) {
        SendA(x%2);
        x /= 2;
    }
}

void run() {
    pii para;
    while (true) {
        if (pq.empty())
            return;
        para = pq.top();
        if (!odw[para.second])
            break;
        pq.pop();
    }
    int dis = para.first, v = para.second;
    mydist = dis;
    myindx = v;
    encode(dis-LD, 9);
    indx = false; poz = 9, pot = 0, val = 0;
}

void updateEdges(int v) {
    odw[v] = 1;
    for (auto [u, d] : edges[v]) {
        if (dist[u] > dist[v] + d) {
            dist[u] = dist[v] + d;
            pq.push({dist[u], u});
        }
    }
}

}

void ReceiveA(bool bit) {
    val += (1<<pot) * bit;
    pot++;
    poz--;
    if (!poz) {
        if (indx) {
            cerr << "Azer received index " << val << "\n";
            dist[val] = lastdist;
            updateEdges(val);
            run();
        } else {
            cerr << "Azer received distance " << val+LD << "\n";
            cerr << "My " << mydist << "\n";
            lastdist = val + LD;
            if (mydist <= lastdist) {
                LD = mydist;
                cerr << "Time to act! (A)\n";
                updateEdges(myindx);
                encode(myindx, 11);
                run();
            } else {
                LD = lastdist;
                cerr << "Not my turn (A)\n";
                indx = true; poz = 11, pot = 0, val = 0;
            }
        }
    }
}

void InitA(int N, int A, std::vector<signed> U, std::vector<signed> V, std::vector<signed> C) {
    gl_N = N;
    for (int i = 0; i < N; i++) {
        dist[i] = 1000000001;
        pq.push({dist[i], i});
    }
    for (int i = 0; i < A; i++) {
        edges[U[i]].PB({V[i], C[i]});
        edges[V[i]].PB({U[i], C[i]});
    }
    dist[0] = 0;
    pq.push({0, 0});
    run();
}

vector<signed> Answer() {
    vector<signed> ans;
    for (int i = 0; i < gl_N; i++) {
        ans.PB(dist[i]);
    }
    return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
#define PB push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

namespace {

vector<pii> edges[2002];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[1000002], odw[1000002];
int lastdist, mydist, myindx;
int LD = 0;
bool indx;
int poz, pot, val, gl_N;

void encode(int x, int format) {
    if (x > (1<<format)) x = (1<<format) - 3;
    for (int i = 0; i < format; i++) {
        SendB(x%2);
        x /= 2;
    }
}

void run() {
    pii para;
    while (true) {
        if (pq.empty())
            return;
        para = pq.top();
        if (!odw[para.second])
            break;
        pq.pop();
    }
    int dis = para.first, v = para.second;
    mydist = dis;
    myindx = v;
    encode(dis-LD, 9);
    indx = false; poz = 9, pot = 0, val = 0;
}

void updateEdges(int v) {
    odw[v] = 1;
    for (auto [u, d] : edges[v]) {
        if (dist[u] > dist[v] + d) {
            dist[u] = dist[v] + d;
            pq.push({dist[u], u});
        }
    }
}

}

void ReceiveB(bool bit) {
    val += (1<<pot) * bit;
    pot++;
    poz--;
    if (!poz) {
        if (indx) {
            cerr << "Baihan received index " << val << "\n";
            dist[val] = lastdist;
            updateEdges(val);
            run();
        } else {
            cerr << "Baihan received distance " << val+LD << "\n";
            cerr << "My " << mydist << "\n";
            lastdist = val + LD;
            if (mydist < lastdist) {
                cerr << "Time to act! (B)\n";
                LD = mydist;
                updateEdges(myindx);
                encode(myindx, 11);
                run();
            } else {
                cerr << "Not my turn (B)\n";
                LD = lastdist;
                indx = true; poz = 11, pot = 0, val = 0;
            }
        }
    }
}

void InitB(int N, int B, std::vector<int> U, std::vector<int> V, std::vector<int> D) {
    gl_N = N;
    for (int i = 0; i < N; i++) {
        dist[i] = 1000000001;
        pq.push({dist[i], i});
    }
    for (int i = 0; i < B; i++) {
        edges[U[i]].PB({V[i], D[i]});
        edges[V[i]].PB({U[i], D[i]});
    }
    dist[0] = 0;
    pq.push({0, 0});
    run();
}

• 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