Submission #1014938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014938		efishel	Two Transportations (JOI19_transportations)	C++17	0 / 100	3000 ms	664 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

namespace {
const ll MAXN = 2E3+16, INF = (1<<20)-1;

int n;
int cou;
ll curU, curW;
priority_queue <pair <ll, ll> > pq;
vector <pair <ll, ll> > adj[MAXN];
bool vis[MAXN];
ll unex;
vll dis;

pair <ll, ll> getTop () {
    while (pq.size() && vis[pq.top().second]) pq.pop();
    if (pq.size()) return { -pq.top().first, pq.top().second };
    return { INF, MAXN-4 };
}

void propTop () {
    ll u = getTop().second; pq.pop();
    assert(!vis[u]);
    vis[u] = true; unex--;
    for (auto [v, w] : adj[u]) {
        if (dis[v] <= dis[u]+w) continue;
        dis[v] = dis[u]+w;
        pq.push({ -dis[v], v });
    }
}

void mySend (ll x, ll bits) { for (ll i = 0; i < bits; i++) SendA(x>>i&1); }

void sendTop () {
    mySend(getTop().first, 20);
    mySend(getTop().second, 11);
}

void readAll () {
    if (curW < getTop().first) { // other wins, inserts in current graph, expands
        dis[curU] = curW;
        pq.push({ -curW, curU });
        propTop();
    } else if (curW >= getTop().first) { // you win, other should prop well, you just normal
        propTop();
    }
    if (unex) sendTop();
}

}  // namespace

void InitA (int n, int m, vi us, vi vs, vi wws) {
    ::n = n;
    unex = n;
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back({ vs[i], wws[i] });
        adj[vs[i]].push_back({ us[i], wws[i] });
    }
    cou = 0;
    curU = 0;
    curW = 0;
    dis = vll(n, INF);
    dis[0] = 0;
    pq.push({ -dis[0], 0 });
    propTop();
    if (unex) sendTop();
}

void ReceiveA (bool x) {
    if (cou%31 < 20) curW |= x<<cou%31;
    else curU |= x<<(cou%31-20);
    if (cou%31 == 30) { readAll(); curW = 0; curU = 0; }
    cou++;
}

vi Answer () {
    return vi(dis.begin(), dis.end());
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

namespace {
const ll MAXN = 2E3+16, INF = (1<<20)-1;

int n;
int cou;
ll curU, curW;
priority_queue <pair <ll, ll> > pq;
vector <pair <ll, ll> > adj[MAXN];
bool vis[MAXN];
ll unex;
vll dis;

pair <ll, ll> getTop () {
    while (pq.size() && vis[pq.top().second]) pq.pop();
    if (pq.size()) return { -pq.top().first, pq.top().second };
    return { INF, MAXN-4 };
}

void propTop () {
    ll u = getTop().second; pq.pop();
    assert(!vis[u]);
    vis[u] = true; unex--;
    for (auto [v, w] : adj[u]) {
        if (dis[v] <= dis[u]+w) continue;
        dis[v] = dis[u]+w;
        pq.push({ -dis[v], v });
    }
}

void mySend (ll x, ll bits) { for (ll i = 0; i < bits; i++) SendB(x>>i&1); }

void sendTop () {
    mySend(getTop().first, 20);
    mySend(getTop().second, 11);
}

void readAll () {
    if (curW <= getTop().first) { // other wins, inserts in current graph, expands
        dis[curU] = curW;
        pq.push({ -curW, curU });
        propTop();
    } else if (curW > getTop().first) { // you win, other should prop well, you just normal
        propTop();
    }
    if (unex) sendTop();
}

}  // namespace

void InitB (int n, int m, vi us, vi vs, vi wws) {
    ::n = n;
    unex = n;
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back({ vs[i], wws[i] });
        adj[vs[i]].push_back({ us[i], wws[i] });
    }
    cou = 0;
    curU = 0;
    curW = 0;
    dis = vll(n, INF);
    dis[0] = 0;
    pq.push({ -dis[0], 0 });
    propTop();
    if (unex) sendTop();
}

void ReceiveB (bool x) {
    if (cou%31 < 20) curW |= x<<cou%31;
    else curU |= x<<(cou%31-20);
    if (cou%31 == 30) { readAll(); curW = 0; curU = 0; }
    cou++;
}

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