Submission #1157174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157174		irmuun	Two Transportations (JOI19_transportations)	C++20	0 / 100	198 ms	13632 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define pii pair<int,int>

namespace {

int N;
int cnt;

const int maxq=58000,maxn=2000,inf=1e9;

bool used[maxn];

bool stop=true;

int cur=0,pos=0,last=-1;
bool in[maxq];
int dist[maxn];

vector<pii>adj[maxn];

void send_number(int x,int bit){
    for(int i=0;i<bit;i++){
        SendA(x&(1<<i)?true:false);
    }
}

priority_queue<pii,vector<pii>,greater<pii>>pq;

void find_next(){
    stop=false;
    if(pq.empty()) return;
    while(!pq.empty()){
        auto [d,i]=pq.top();
        pq.pop();
        if(dist[i]!=d){
            continue;
        }
        for(auto [w,j]:adj[i]){
            if(dist[i]+w<dist[j]){
                dist[j]=dist[i]+w;
                pq.push({dist[j],j});
            }
        }
        if(!used[i]){
            cerr<<"sendA : "<<i<<' '<<d<<endl;
            used[i]=true;
            send_number(i,11);
            send_number(d,20);
        }
    }
    stop=true;
}

}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V,vector<int> C) {
    ::N = N;
    fill(dist,dist+N,inf);
    fill(used,used+N,false);
    dist[0]=0;
    pq.push({0,0});
    for(int i=0;i<A;i++){
        adj[U[i]].pb({C[i],V[i]});
        adj[V[i]].pb({C[i],U[i]});
        // cerr<<"A : "<<U[i]<<' '<<V[i]<<' '<<C[i]<<"\n";
    }
    for(int i=0;i<N;i++){
        sort(all(adj[i]));
    }
    find_next();
}

void ReceiveA(bool x) {
    in[cnt++]=x;
    if(cnt%31==0){//full
        int node=0,val=0;
        for(int i=0;i<11;i++){
            node+=(in[pos+i]?(1<<i):0);
        }
        pos+=11;
        for(int i=0;i<20;i++){
            val+=(in[pos+i]?(1<<i):0);
        }
        cerr<<"In A : "<<node<<' '<<val<<endl;
        pos+=20;
        if(val<dist[node]){
            used[node]=true;
            dist[node]=val;
            pq.push({val,node});
        }
        last=node;
        if(stop==true){
            find_next();
        }
    }
}

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

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define pii pair<int,int>

namespace {

int N;
int cnt;

const int maxq=58000,maxn=2000,inf=1e9;

bool used[maxn];

bool stop=true;

int cur=0,pos=0,last=-1;
bool in[maxq];
int dist[maxn];

vector<pii>adj[maxn];

int node=-1;

void send_number(int x,int bit){
    for(int i=0;i<bit;i++){
        SendB(x&(1<<i)?true:false);
    }
}

priority_queue<pii,vector<pii>,greater<pii>>pq;

void find_next(){
    stop=false;
    if(pq.empty()) return;
    while(!pq.empty()){
        auto [d,i]=pq.top();
        pq.pop();
        if(dist[i]!=d){
            continue;
        }
        for(auto [w,j]:adj[i]){
            if(dist[i]+w<dist[j]){
                dist[j]=dist[i]+w;
                pq.push({dist[j],j});
            }
        }
        if(!used[i]){
            cerr<<"sendB : "<<i<<' '<<d<<endl;
            used[i]=true;
            send_number(i,11);
            send_number(d,20);
        }
    }
    stop=true;
}

}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
    ::N = N;
    fill(dist,dist+N,inf);
    fill(used,used+N,false);
    for(int i=0;i<B;i++){
        adj[S[i]].pb({D[i],T[i]});
        adj[T[i]].pb({D[i],S[i]});
    }
    for(int i=0;i<N;i++){
        sort(all(adj[i]));
    }
}

void ReceiveB(bool y) {
    in[cnt++]=y;
    if(cnt%31==0){//full
        int node=0,val=0;
        for(int i=0;i<11;i++){
            node+=(in[pos+i]?(1<<i):0);
        }
        pos+=11;
        for(int i=0;i<20;i++){
            val+=(in[pos+i]?(1<<i):0);
        }
        pos+=20;
        cerr<<"In B : "<<node<<' '<<val<<endl;
        if(val<dist[node]){
            used[node]=true;
            dist[node]=val;
            pq.push({val,node});
        }
        if(stop==true){
            find_next();
        }
    }
}

• 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