Submission #473176

#	Time	Username	Problem	Language	Result	Execution time	Memory
473176		jk410	Two Transportations (JOI19_transportations)	C++17	38 / 100	794 ms	35364 KiB

Azer

#include "Azer.h"
#include <iostream>
#include <vector>
using namespace std;
namespace {
    struct edge{
        int v,cost;
    };
    const int INF=1e9,cnt_v=10,cnt_cost=19;
    int N,tmp_v,cnt_query,cnt_receive,v_receive,cost_receive;
    bool flag;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    void my_sendA(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendA(x&(1<<i));
    }
    int get_closest(){
        int v=-1;
        for (int i=0; i<N; i++){
            if (Used[i])
                continue;
            if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
                v=i;
        }
        return v;
    }
    void update_edge(int v){
        for (edge i:Edge[v])
            Dist[i.v]=min(Dist[i.v],Dist[v]+i.cost);
    }
    void send_closest(int v){
        my_sendA(cnt_v,v);
        if (v!=-1)
            my_sendA(cnt_cost,Dist[v]);
        else
            my_sendA(cnt_cost,0);
    }
}
void ReceiveA(bool x){
    if (!flag){
        v_receive+=x*(1<<cnt_receive);
        cnt_receive++;
    }
    else{
        cost_receive+=x*(1<<cnt_receive);
        cnt_receive++;
    }
    if (!flag&&cnt_receive==cnt_v){
        flag=true;
        cnt_receive=0;
    }
    if (flag&&cnt_receive==cnt_cost){
        flag=false;
        Dist[v_receive]=min(Dist[v_receive],cost_receive);
        Used[v_receive]=true;
        update_edge(v_receive);
        cnt_query++;
        tmp_v=get_closest();
        if (cnt_query<N-1)
            send_closest(tmp_v);
        v_receive=cost_receive=cnt_receive=0;
    }
}
void InitA(int n,int a,vector<int> u,vector<int> v,vector<int> c){
    N=n;
    cnt_query=cnt_receive=v_receive=cost_receive=0;
    flag=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    for (int i=0; i<a; i++){
        Edge[u[i]].push_back({v[i],c[i]});
        Edge[v[i]].push_back({u[i],c[i]});
    }
    for (int i=0; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    Dist[0]=0;
    Used[0]=true;
    update_edge(0);
    tmp_v=get_closest();
    if (N>1)
        send_closest(tmp_v);
}
vector<int> Answer(){
    return Dist;
}

Baijan

#include "Baijan.h"
#include <iostream>
#include <vector>
using namespace std;
namespace {
    struct edge{
        int v,cost;
    };
    const int INF=1e9,cnt_v=10,cnt_cost=19;
    int N,tmp_v,cnt_receive,v_receive,cost_receive;
    bool flag;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    void my_sendB(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendB(x&(1<<i));
    }
    int get_closest(){
        int v=-1;
        for (int i=0; i<N; i++){
            if (Used[i])
                continue;
            if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
                v=i;
        }
        return v;
    }
    void update_edge(int v){
        for (edge i:Edge[v])
            Dist[i.v]=min(Dist[i.v],Dist[v]+i.cost);
    }
    void send_closest(int v){
        my_sendB(cnt_v,v);
        my_sendB(cnt_cost,Dist[v]);
    }
}
void ReceiveB(bool y){
    if (!flag){
        v_receive+=y*(1<<cnt_receive);
        cnt_receive++;
    }
    else{
        cost_receive+=y*(1<<cnt_receive);
        cnt_receive++;
    }
    if (!flag&&cnt_receive==cnt_v){
        if (v_receive==(1<<cnt_v)-1)
            v_receive=-1;
        flag=true;
        cnt_receive=0;
    }
    if (flag&&cnt_receive==cnt_cost){
        flag=false;
        if (tmp_v==-1||v_receive!=-1&&Dist[tmp_v]>cost_receive){
            tmp_v=v_receive;
            Dist[tmp_v]=cost_receive;
        }
        Used[tmp_v]=true;
        update_edge(tmp_v);
        send_closest(tmp_v);
        tmp_v=get_closest();
        v_receive=cost_receive=cnt_receive=0;
    }
}
void InitB(int n,int b,vector<int> s,vector<int> t,vector<int> d){
    N=n;
    cnt_receive=v_receive=cost_receive=0;
    flag=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    for (int i=0; i<b; i++){
        Edge[s[i]].push_back({t[i],d[i]});
        Edge[t[i]].push_back({s[i],d[i]});
    }
    for (int i=0; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    Dist[0]=0;
    Used[0]=true;
    update_edge(0);
    tmp_v=get_closest();
}

Compilation message (stderr)

Azer.cpp: In function 'int {anonymous}::get_closest()':
Azer.cpp:24:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |             if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
      |                 ~~~~~^~~~~~~~~~~~~~

Baijan.cpp: In function 'int {anonymous}::get_closest()':
Baijan.cpp:24:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   24 |             if (v==-1&&Dist[i]!=INF||Dist[v]>Dist[i])
      |                 ~~~~~^~~~~~~~~~~~~~
Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:55:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |         if (tmp_v==-1||v_receive!=-1&&Dist[tmp_v]>cost_receive){
      |                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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