제출 #1288394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288394		Aviansh	Two Transportations (JOI19_transportations)	C++20	100 / 100	679 ms	58284 KiB

Azer

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

using namespace std;

namespace {

    int n;
    int dist[58005];
    vector<array<int,2>>g[58005];
    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
    int mxdist = 0;

    string curdis = "";
    string curloc = "";

    int cn = 1;

}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    n = N;
    for (int i = 0; i < A; ++i) {
        g[U[i]].push_back({V[i],C[i]});
        g[V[i]].push_back({U[i],C[i]});
    }
    fill(dist,dist+58005,1e9);
    dist[0]=0;
    for(array<int,2>a:g[0]){
        pq.push({a[1],a[0]});
    }
    if(pq.size()){
        int dis = pq.top()[0];
        dis-=mxdist;
        for(int i = 0;i<9;i++){
            if((1<<i)&dis){
                SendA(1);
            }
            else{
                SendA(0);
            }
        }
    }
    else{
        for(int i = 0;i<9;i++){
            SendA(1);
        }
    }
}

void ReceiveA(bool x) {
    while(pq.size()&&dist[pq.top()[1]]!=1e9){
        pq.pop();
    }
    if(cn>=n)
        return;
    if(curdis.size()<9){
        if(x){
            curdis+="1";
        }
        else{
            curdis+="0";
        }
        if(curdis.size()==9){
            //just received entire dist
            int curdist = 0;
            for(int i = 0;i<9;i++){
                if(curdis[i]=='1'){
                    curdist+=(1<<i);
                }
            }
            cerr << "A received dist: " << curdist << "\n";
            if(!(pq.size()==0)&&mxdist+curdist>=pq.top()[0]){
                //must use current
                array<int,2>a = pq.top();
                pq.pop();
                cerr << "A decides to send loc: " << a[1] << "\n";
                for(int i = 0;i<11;i++){
                    if(a[1]&(1<<i)){
                        SendA(1);
                    }
                    else{
                        SendA(0);
                    }
                }
                dist[a[1]]=a[0];
                cn++;
                for(array<int,2>e:g[a[1]]){
                    pq.push({a[0]+e[1],e[0]});
                }
                mxdist=a[0];
                while(pq.size()&&dist[pq.top()[1]]!=1e9){
                    pq.pop();
                }
                if(pq.size()){
                    int dis = pq.top()[0];
                    dis-=mxdist;
                    for(int i = 0;i<9;i++){
                        if((1<<i)&dis){
                            SendA(1);
                        }
                        else{
                            SendA(0);
                        }
                    }
                }
                else{
                    for(int i = 0;i<9;i++){
                        SendA(1);
                    }
                }
                curdis="";
            }
        }
    }
    else{
        //new loc being received
        if(curloc.size()<11){
            if(x){
                curloc+="1";
            }
            else{
                curloc+="0";
            }
        }
        if(curloc.size()==11){
            int loc = 0;
            for(int i = 0;i<11;i++){
                if(curloc[i]=='1'){
                    loc+=(1<<i);
                }
            }
            cerr << "A received loc: " << loc << "\n";
            int curdist = 0;
            for(int i = 0;i<9;i++){
                if(curdis[i]=='1'){
                    curdist+=(1<<i);
                }
            }
            cerr << "A already had dist: " << curdist << "\n";
            array<int,2>a = {mxdist+curdist,loc};
            dist[a[1]]=a[0];
            cn++;
            for(array<int,2>e:g[a[1]]){
                pq.push({a[0]+e[1],e[0]});
            }
            mxdist=a[0];
            while(pq.size()&&dist[pq.top()[1]]!=1e9){
                pq.pop();
            }
            if(pq.size()){
                int dis = pq.top()[0];
                dis-=mxdist;
                cerr << "A sends the dist: " << dis << " for " << pq.top()[1] << "\n";
                for(int i = 0;i<9;i++){
                    if((1<<i)&dis){
                        SendA(1);
                    }
                    else{
                        SendA(0);
                    }
                }
            }
            else{
                cerr << "A sends infinite\n";
                for(int i = 0;i<9;i++){
                    SendA(1);
                }
            }
            curdis="";
            curloc="";
        }
    }
}

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

Baijan

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

using namespace std;

namespace {

    int n;
    int dist[58005];
    vector<array<int,2>>g[58005];
    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
    int mxdist = 0;
    int cn = 1;

    string curdis = "";
    string curloc = "";
}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
    n = N;
    for (int i = 0; i < B; ++i) {
        g[S[i]].push_back({T[i],D[i]});
        g[T[i]].push_back({S[i],D[i]});
    }
    fill(dist,dist+58005,1e9);
    dist[0]=0;
    for(array<int,2>a:g[0]){
        pq.push({a[1],a[0]});
    }
    if(pq.size()){
        int dis = pq.top()[0];
        dis-=mxdist;
        for(int i = 0;i<9;i++){
            if((1<<i)&dis){
                SendB(1);
            }
            else{
                SendB(0);
            }
        }
    }
    else{
        for(int i = 0;i<9;i++){
            SendB(1);
        }
    }
}

void ReceiveB(bool x) {
    while(pq.size()&&dist[pq.top()[1]]!=1e9){
        pq.pop();
    }
    if(cn>=n){
        return;
    }
    if(curdis.size()<9){
        if(x){
            curdis+="1";
        }
        else{
            curdis+="0";
        }
        if(curdis.size()==9){
            //just received entire dist
            int curdist = 0;
            for(int i = 0;i<9;i++){
                if(curdis[i]=='1'){
                    curdist+=(1<<i);
                }
            }
            cerr << "B received dist: " << curdist << "\n";
            if(!(pq.size()==0)&&mxdist+curdist>pq.top()[0]){
                //must use current
                array<int,2>a = pq.top();
                pq.pop();
                cerr << "B decides to send loc: " << a[1] << "\n";
                for(int i = 0;i<11;i++){
                    if(a[1]&(1<<i)){
                        SendB(1);
                    }
                    else{
                        SendB(0);
                    }
                }
                dist[a[1]]=a[0];
                cn++;
                for(array<int,2>e:g[a[1]]){
                    pq.push({a[0]+e[1],e[0]});
                }
                mxdist=a[0];
                while(pq.size()&&dist[pq.top()[1]]!=1e9){
                    pq.pop();
                }
                if(pq.size()){
                    int dis = pq.top()[0];
                    dis-=mxdist;
                    for(int i = 0;i<9;i++){
                        if((1<<i)&dis){
                            SendB(1);
                        }
                        else{
                            SendB(0);
                        }
                    }
                }
                else{
                    for(int i = 0;i<9;i++){
                        SendB(1);
                    }
                }
                curdis="";
            }
        }
    }
    else{
        //new loc being received
        if(curloc.size()<11){
            if(x){
                curloc+="1";
            }
            else{
                curloc+="0";
            }
        }
        if(curloc.size()==11){
            int loc = 0;
            for(int i = 0;i<11;i++){
                if(curloc[i]=='1'){
                    loc+=(1<<i);
                }
            }
            cerr << "B received loc: " << loc << "\n";
            int curdist = 0;
            for(int i = 0;i<9;i++){
                if(curdis[i]=='1'){
                    curdist+=(1<<i);
                }
            }
            cerr << "B already had dist: " << curdist << "\n";
            array<int,2>a = {mxdist+curdist,loc};
            dist[a[1]]=a[0];
            cn++;
            for(array<int,2>e:g[a[1]]){
                pq.push({a[0]+e[1],e[0]});
            }
            mxdist=a[0];
            while(pq.size()&&dist[pq.top()[1]]!=1e9){
                pq.pop();
            }
            if(pq.size()){
                int dis = pq.top()[0];
                dis-=mxdist;
                cerr << "B sends the dist: " << dis << " for " << pq.top()[1] << "\n";
                for(int i = 0;i<9;i++){
                    if((1<<i)&dis){
                        SendB(1);
                    }
                    else{
                        SendB(0);
                    }
                }
            }
            else{
                cerr << "B sends infinite\n";
                for(int i = 0;i<9;i++){
                    SendB(1);
                }
            }
            curdis="";
            curloc="";
        }
    }
}

• 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