Submission #478828

#	Time	Username	Problem	Language	Result	Execution time	Memory
478828		jk410	Two Transportations (JOI19_transportations)	C++17	100 / 100	921 ms	49336 KiB

Azer

#include "Azer.h"
#include <vector>
#include <queue>
using namespace std;
namespace{
    struct edge{
        int v,cost;
        bool operator<(const edge &t)const{
            return cost>t.cost;
        }
    };
    const int INF=1e9,cnt_cost=9,cnt_v=11;
    int N,cnt,cnt_query,receive_cost,receive_v,you_cost,sent_cost;
    edge closest;
    bool cur_mode;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    priority_queue<edge> Q;
    void my_send(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendA(x&(1<<i));
    }
    edge get_closest(){
        while (!Q.empty()){
            if (!Used[Q.top().v])
                return Q.top();
            Q.pop();
        }
        return {-1,-1};
    }
    void update_and_send(edge t){
        Dist[t.v]=t.cost;
        Used[t.v]=true;
        if (cnt_query==N-1)
            return;
        for (edge i:Edge[t.v]){
            if (Used[i.v])
                continue;
            Q.push({i.v,Dist[t.v]+i.cost});
        }
        closest=get_closest();
        if (closest.v==-1)
            my_send(cnt_cost,-1);
        else
            my_send(cnt_cost,closest.cost-sent_cost);
    }
}
void InitA(int n,int a,vector<int> u,vector<int> v,vector<int> c){
    N=n;
    cnt=cnt_query=receive_cost=receive_v=sent_cost=0;
    cur_mode=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    for (int i=0; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    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]});
    }
    update_and_send({0,0});
}
void ReceiveA(bool x){
    if (!cur_mode&&cnt<cnt_cost){
        receive_cost+=x*(1<<cnt);
        cnt++;
    }
    if (cur_mode&&cnt<cnt_v){
        receive_v+=x*(1<<cnt);
        cnt++;
    }
    if (!cur_mode&&cnt==cnt_cost){
        cnt_query++;
        if (receive_cost!=(1<<cnt_cost)-1)
            you_cost=sent_cost+receive_cost;
        if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>=closest.cost){
            Q.pop();
            my_send(cnt_v,closest.v);
            sent_cost=closest.cost;
            update_and_send(closest);
        }
        else{
            sent_cost=you_cost;
            cur_mode=true;
        }
        cnt=receive_cost=0;
    }
    if (cur_mode&&cnt==cnt_v){
        update_and_send({receive_v,you_cost});
        cnt=receive_v=0;
        cur_mode=false;
    }
}
vector<int> Answer(){
    return Dist;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <queue>
using namespace std;
namespace{
    struct edge{
        int v,cost;
        bool operator<(const edge &t)const{
            return cost>t.cost;
        }
    };
    const int INF=1e9,cnt_cost=9,cnt_v=11;
    int N,cnt,receive_cost,receive_v,you_cost,sent_cost;
    edge closest;
    bool cur_mode;
    vector<int> Dist;
    vector<bool> Used;
    vector<vector<edge>> Edge;
    priority_queue<edge> Q;
    void my_send(int cnt,int x){
        for (int i=0; i<cnt; i++)
            SendB(x&(1<<i));
    }
    edge get_closest(){
        while (!Q.empty()){
            if (!Used[Q.top().v])
                return Q.top();
            Q.pop();
        }
        return {-1,-1};
    }
    void update_closest(edge t){
        Dist[t.v]=t.cost;
        Used[t.v]=true;
        for (edge i:Edge[t.v]){
            if (Used[i.v])
                continue;
            Q.push({i.v,Dist[t.v]+i.cost});
        }
    }
}
void InitB(int n,int b,vector<int> s,vector<int> t,vector<int> d){
    N=n;
    cnt=receive_cost=receive_v=sent_cost=0;
    cur_mode=false;
    Dist.resize(N);
    Used.resize(N);
    Edge.resize(N);
    for (int i=1; i<N; i++){
        Dist[i]=INF;
        Used[i]=false;
    }
    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]});
    }
    update_closest({0,0});
}
void ReceiveB(bool y){
    if (!cur_mode&&cnt<cnt_cost){
        receive_cost+=y*(1<<cnt);
        cnt++;
    }
    if (cur_mode&&cnt<cnt_v){
        receive_v+=y*(1<<cnt);
        cnt++;
    }
    if (!cur_mode&&cnt==cnt_cost){
        if (receive_cost!=(1<<cnt_cost)-1)
            you_cost=sent_cost+receive_cost;
        closest=get_closest();
        if (closest.v==-1)
            my_send(cnt_cost,-1);
        else
            my_send(cnt_cost,closest.cost-sent_cost);
        if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>closest.cost){
            Q.pop();
            update_closest(closest);
            sent_cost=closest.cost;
            my_send(cnt_v,closest.v);
        }
        else{
            sent_cost=you_cost;
            cur_mode=true;
        }
        cnt=receive_cost=0;
    }
    if (cur_mode&&cnt==cnt_v){
        update_closest({receive_v,you_cost});
        cnt=receive_v=0;
        cur_mode=false;
    }
}

Compilation message (stderr)

Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:79:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   79 |         if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>=closest.cost){
      |                                            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:76:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   76 |         if (receive_cost==(1<<cnt_cost)-1||closest.cost!=-1&&you_cost>closest.cost){
      |                                            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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