제출 #1232534

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

Azer

#pragma GCC optimize("Ofast,unroll-loops")
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ff first
#define ss second
#define ln "\n"

const ll INF = 2e9;

static int n;
static vector<ll> dist;
static ll sf=0, finish=0;
static vector<vector<pair<ll, ll>>> gr;
array<ll, 3> process(){
    for (ll i=0; i<n; i++){
        if (dist[i]!=INF) sf=max(sf, dist[i]);
    }
    bool unset=0;
    for (ll i=0; i<n; i++){
        if (dist[i]==INF) unset=1;
    }
    if (!unset) finish=1;
    array<ll, 3> best={INF, -1, -1};
    for (ll i=0; i<n; i++){
        if (dist[i]!=INF){
            for (auto [v, w]:gr[i]){
                if (dist[v]==INF) best=min(best, {dist[i]+w-sf, dist[i]+w, v});
            }
        }
    }
    return best;
}
static array<ll, 3> send = {-1, -1, -1};
static vector<ll> buffer;

void handleNewIter(){
    array<ll, 3> nw = process();
    if (finish) return;
    // cout << "A sending weight: " << nw[0] << " + " << sf << endl;
    for (ll i=0; i<9; i++){
        if ((1<<i)&nw[0] or nw[0]==INF) SendA(1);
        else SendA(0);
    }
    send=nw;
}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n=N; finish=0;
    buffer.clear(); gr.assign(n, vector<pair<ll, ll>>());
    dist.assign(n, INF); dist[0]=0; sf=0;
    for (ll i=0; i<A; i++){
        gr[U[i]].push_back({V[i], C[i]});
        gr[V[i]].push_back({U[i], C[i]});
    }
    handleNewIter();
}


void ReceiveA(bool x) {
    if (finish) return;
    buffer.push_back(x);
    if (buffer.size()==9){
        ll w = 0;
        for (ll i=0; i<9; i++){
            if (buffer[i]) w+=(1<<i);
        }
        // cout << "A received weight: " << w << " + " << sf << endl;
        if (w<send[0]){
            // cout << "A Waiting for full data " << endl;
            return;
        }else{
            if (send[0]==INF){
                finish=1; return;
            }
            // cout << "A sending vertex: " << send[2] << endl;
            for (ll i=0; i<11; i++){
                if ((1<<i)&send[2]) SendA(1);
                else SendA(0);
            }
            dist[send[2]]=send[1];
        }
        buffer.clear(); handleNewIter();
    }else if (buffer.size()==20){
        ll w = sf; for (ll i=0; i<9; i++){
            if (buffer[i]) w+=(1<<i);
        }
        ll u=0; for (ll i=9; i<20; i++){
            if (buffer[i]) u+=(1<<(i-9));
        }
        // cout << "A received: " << u << " & " << w << " - " << sf << endl;
        dist[u]=w; buffer.clear();
        handleNewIter();
    }
}

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

Baijan

#pragma GCC optimize("Ofast,unroll-loops")
#include "Baijan.h"
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll INF = 2e9;

static vector<vector<pair<ll, ll>>> gr;
static int n;
static vector<ll> dist;

static ll sf = 0, finish=0;

static array<ll, 3> process(){
    for (ll i=0; i<n; i++){
        if (dist[i]!=INF) sf=max(sf, dist[i]);
    }
    bool unset=0;
    for (ll i=0; i<n; i++){
        if (dist[i]==INF) unset=1;
    }
    if (unset==0) {
        finish=1;
    }
    array<ll, 3> best = {INF, -1, -1};
    for (ll i=0; i<n; i++){
        if (dist[i]!=INF){
            for (auto [v, w]:gr[i]){
                if (dist[v]==INF) best=min(best, {dist[i]+w-sf, dist[i]+w, v});
            }
        }
    }
    return best;
}

static vector<bool> buffer;

static array<ll, 3> send = {-1, -1, -1};

static void newIter(){
    buffer.clear();
    send=process();
}

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
    n=N; gr.assign(n, vector<pair<ll, ll>>()); finish=0;
    dist.assign(n, INF); dist[0]=0; sf=0;
    for (ll i=0; i<B; i++){
        gr[S[i]].push_back({T[i], D[i]});
        gr[T[i]].push_back({S[i], D[i]});
    }
    newIter();
}

void ReceiveB(bool y) {
    if (finish) return;
    buffer.push_back(y);
    if (buffer.size()==9){
        ll w=0;
        for (ll i=0; i<9; i++){
            if (buffer[i]) w+=(1<<i);
        }
        // cout << "B received: " << w << " aka " << w+sf << endl;
        if (w<=send[0]){
            for (ll i=0; i<9; i++){
                if (send[0]>=INF or send[0]&(1<<i)) SendB(1);
                else SendB(0);
            }
            // cout << "B sending (9): " << send[0] << " based on " << send[1] << " - " << sf << endl;
            return;
        }else{
            for (ll i=0; i<9; i++){
                if (send[0]&(1<<i)) SendB(1);
                else SendB(0);
            }
            for (ll i=0; i<11; i++){
                if (send[2]&(1<<i)) SendB(1);
                else SendB(0);
            }
            // cout << "B sending (20): " << send[0] << " " << send[2] << " based on " << send[1] << " - " << sf << endl;
            dist[send[2]]=send[1];
            newIter();
        }
    }else if (buffer.size()==20){
        ll w=sf;
        for (ll i=0; i<9; i++){
            if (buffer[i]) w+=(1<<i);
        }
        ll u=0;
        for (ll i=9; i<20; i++){
            if (buffer[i]) u+=(1<<(i-9));
        }
        // cout << "B received (20): " << u << " " << w << endl;
        dist[u]=w; newIter();
    }
}

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