제출 #1227574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227574		MarwenElarbi	Two Transportations (JOI19_transportations)	C++17	38 / 100	257 ms	35756 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
// A
#define fi first
#define se second
namespace {
    int n_a;
    long long dis_a[2500];
    int j_a=0;
    int node_a=0;
    set<int> st_a;
    int d_a=0;
    vector<pair<int,int>> adj_a[2500];
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq_a;
    void senda(){
        if(pq_a.empty()){
            for (int i = 0; i < 11; ++i)
            {
                SendA(true);
            }
            for (int i = 0; i < 20; ++i)
            {
                SendA(true);
            }
        }else{
            int u=pq_a.top().se;
            int d=pq_a.top().fi;
            for (int i = 0; i < 11; ++i)
            {
                SendA((1<<i)&u);
            }
            for (int i = 0; i < 20; ++i)
            {
                SendA((1<<i)&d);
            }
            pq_a.pop();
        }
    }
}  // namespace

    void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
        n_a = N;
        for (int i = 0; i < N; ++i)
        {
            dis_a[i]=1e9;
        }
        for (int i = 0; i < A; ++i)
        {
            adj_a[U[i]].push_back({V[i],C[i]});
            adj_a[V[i]].push_back({U[i],C[i]});
        }
        pq_a.push({0,0});
        dis_a[0]=0;
        for (auto u:adj_a[0]) {
            pq_a.push({u.se,u.fi});
            dis_a[u.fi]=u.se;
        }
        st_a.insert(0);
        senda();
    }

    void ReceiveA(bool x) {
        if(0<=j_a&&j_a<11){
            node_a+=(x<<j_a);
        }else if(11<=j_a&&j_a<31){
            d_a+=(x<<(j_a-11));
        }
        j_a++;
        if(j_a==31){
            //cout << "A" <<" "<<node_a<<" "<<d_a<<endl;
            j_a=0;
            if(node_a<2000){
                if(d_a<dis_a[node_a]){
                    dis_a[node_a]=d_a;
                    pq_a.push({d_a,node_a});
                    for(auto u:adj_a[node_a]){
                        if(dis_a[u.fi]<=d_a+u.se) continue;
                        dis_a[u.fi]=d_a+u.se;
                        pq_a.push({dis_a[u.fi],u.fi});
                    }
                }
            }
            while(!pq_a.empty()&&(st_a.count(pq_a.top().se))) pq_a.pop();
            //cout <<pq_a.top().fi<<endl;
            if(!pq_a.empty()){
                node_a=pq_a.top().se;
                d_a=pq_a.top().fi;
                //pq_a.pop();
                for(auto u:adj_a[node_a]){
                    if(dis_a[u.fi]<=d_a+u.se) continue;
                    dis_a[u.fi]=d_a+u.se;
                    pq_a.push({dis_a[u.fi],u.fi});
                }
            }
            if(!pq_a.empty()) st_a.insert(pq_a.top().se);
            /*for (int i = 0; i < n_a; ++i)
            {
                cout <<(dis_a[i]==1e9 ? -1 : dis_a[i])<<" ";
            }cout <<endl;*/
            //cout <<dis_a[1]<<endl;
            st_a.insert(node_a);
            senda();
            node_a=0;
            d_a=0;
        }
    }

    std::vector<int> Answer() {
        std::vector<int> ans(n_a);
        for (int k = 0; k < n_a; ++k) {
            ans[k] = dis_a[k];
        }
        return ans;
    }

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
// B
#define fi first
#define se second
namespace {
    int n_b;
    int j_b=0;
    int cnt=0;
    int node_b=0;
    int d_b=0;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq_b;
    vector<pair<int,int>> adj_b[2500];
    long long dis_b[2500];
    set<int> st_b;
    void sendb(){
        if(pq_b.empty()){
            for (int i = 0; i < 11; ++i)
            {
                SendB(true);
            }
            for (int i = 0; i < 20; ++i)
            {
                SendB(true);
            }
        }else{
            int u=pq_b.top().se;
            int d=pq_b.top().fi;
            for (int i = 0; i < 11; ++i)
            {
                SendB((1<<i)&u);
            }
            for (int i = 0; i < 20; ++i)
            {
                SendB((1<<i)&d);
            }
            pq_b.pop();
        }
    }
}  // namespace

    void InitB(int N, int B, std::vector<int> S, std::vector<int> T,std::vector<int> D) {
        n_b=N;
        for (int i = 0; i < B; ++i)
        {
            adj_b[S[i]].push_back({T[i],D[i]});
            adj_b[T[i]].push_back({S[i],D[i]});
        }
        for (int i = 0; i < N; ++i)
        {
            dis_b[i]=1e9;
        }
    }

    void ReceiveB(bool y) {
        if(0<=j_b&&j_b<11){
            node_b+=(y<<j_b);
        }else if(11<=j_b&&j_b<31){
            d_b+=(y<<(j_b-11));
        }
        j_b++;
        cnt+=2;
        if(cnt==57900) return;
        if(j_b==31){
            //cout << "B" << " "<< node_b << " " << d_b <<" "<<st_b.size()<<endl;
            j_b=0;
            if(node_b<2000){
                dis_b[node_b]=d_b;
                st_b.insert(node_b);
                for (auto u:adj_b[node_b])
                {
                    if(dis_b[u.fi]<=d_b+u.se) continue;
                    dis_b[u.fi]=d_b+u.se;
                    pq_b.push({dis_b[u.fi],u.fi});
                }
            }
            /*for (int i = 0; i < n_a; ++i)
            {
                cout <<(dis_b[i]==1e9 ? -1 : dis_b[i])<<" ";
            }cout <<endl;*/
            while(!pq_b.empty()&&st_b.count(pq_b.top().se)){
                pq_b.pop();
            }
            //cout <<pq_b.top().fi<<endl;
            if(!pq_b.empty()){
                for (auto u:adj_b[node_b])
                {
                    if(dis_b[u.fi]<=d_b+u.se) continue;
                    dis_b[u.fi]=d_b+u.se;
                    pq_b.push({dis_b[u.fi],u.fi});
                }
            }
            if(st_b.size() < n_b) sendb();
            else if(st_b.size()==n_b){
                st_b.insert(-1);
                sendb();
            }
            node_b=0;
            d_b=0;
        }
    }

• 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