Submission #787138

#	Time	Username	Problem	Language	Result	Execution time	Memory
787138		oscar1f	Two Transportations (JOI19_transportations)	C++17	0 / 100	6 ms	328 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;

int nbSom,nbAre,INFINI=1000*1000*1000,pos,numAppel=0,temp,dernDist=0,nbFini=1,recevDist=0;
vector<int> rep,deb,fin,prix,dist;
vector<pair<int,int>> adja[2005];

void envoi(int x) {
    if (x==0) {
        SendA(false);
    }
    else {
        SendA(true);
    }
}

int transfo(bool x) {
    if (x==true) {
        return 1;
    }
    return 0;
}

void decompo(int val,int nbBits) {
    for (int i=0;i<nbBits;i++) {
        envoi(val%2);
        val/=2;
    }
}

void calcMeil(int propDist) {
    int posMeil=0,distMeil=INFINI;
    for (int i=0;i<nbSom;i++) {
        if (dist[i]!=-1) {
            while (!adja[i].empty() and dist[adja[i].back().first]!=-1) {
                //cout<<posMeil<<" "<<distMeil<<endl;
                adja[i].pop_back();
            }
            if (!adja[i].empty() and dist[i]+adja[i].back().second<distMeil) {
                distMeil=dist[i]+adja[i].back().second;
                posMeil=adja[i].back().first;
            }
        }
    }
    //cout<<"A : "<<posMeil<<" "<<distMeil<<endl;
    if (distMeil>=propDist) {
        recevDist=1;
        decompo(propDist-dernDist,9);
        dernDist=propDist;
    }
    else {
        decompo(distMeil-dernDist,9);
        dernDist=distMeil;
        dist[posMeil]=distMeil;
        nbFini++;
        if (nbFini==nbSom) {
            rep=dist;
        }
        decompo(posMeil,11);   
    }
}

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    nbSom=N;
    nbAre=A;
    deb=U;
    fin=V;
    prix=C;
    for (int i=0;i<nbAre;i++) {
        adja[deb[i]].push_back({fin[i],prix[i]});
        adja[fin[i]].push_back({deb[i],prix[i]});
    }
    for (int i=0;i<nbSom;i++) {
        sort(adja[i].begin(),adja[i].end(),[](pair<int,int> a,pair<int,int> b) {
            if (a.second>b.second) {
                return true;
            }
            return false;
        });
        /*for (auto j:adja[i]) {
            cout<<j.first<<" "<<j.second<<"   ";
        }
        cout<<endl;*/
    }
    dist.push_back(0);
    for (int i=1;i<nbSom;i++) {
        dist.push_back(-1);
    }    
}

void ReceiveA(bool x) {
    if (recevDist==0) {
        temp+=transfo(x)*(1<<(numAppel));
        numAppel++;
        if (numAppel==9) {
            if (temp!=0) {
                int distMeil=temp+dernDist;
                //cout<<posMeil<<" "<<distMeil<<endl;
                calcMeil(distMeil);
            }
            else {
                calcMeil(INFINI);
            }
            temp=0;
            numAppel=0;
        }
    }
    else {
        temp+=transfo(x)*(1<<(numAppel));
        numAppel++;
        if (numAppel==11) {
            dist[temp]=dernDist;
            nbFini++;
            if (nbFini==nbSom) {
                rep=dist;
            }
            temp=0;
            numAppel=0;
            recevDist=0;
        }
    }
}

vector<int> Answer() {
    /*for (int i:rep) {
        cout<<i<<" ";
    }
    cout<<endl;*/
    return rep;
}

Baijan

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;

int nbSom,nbAre,INFINI=1000*1000*1000,pos,numAppel,temp,dernDist=0,recevDist=0,propDist,propPos;
vector<int> rep,deb,fin,prix,dist;
vector<pair<int,int>> adja[2005];

void envoi(int x) {
    if (x==0) {
        SendB(false);
    }
    else {
        SendB(true);
    }
}

int transfo(bool x) {
    if (x==true) {
        return 1;
    }
    return 0;
}

void decompo(int val,int nbBits) {
    for (int i=0;i<nbBits;i++) {
        envoi(val%2);
        val/=2;
    }
}

void calcMeil() {
    int posMeil=0,distMeil=INFINI;
    for (int i=0;i<nbSom;i++) {
        if (dist[i]!=-1) {
            while (!adja[i].empty() and dist[adja[i].back().first]!=-1) {
                adja[i].pop_back();
            }
            if (!adja[i].empty() and dist[i]+adja[i].back().second<distMeil) {
                distMeil=dist[i]+adja[i].back().second;
                posMeil=adja[i].back().first;
            }
        }
    }
    propDist=distMeil;
    propPos=posMeil;
    if (distMeil==INFINI or distMeil>dernDist+500) {
        distMeil=0;
        posMeil=0;
    }
    else {
        distMeil-=dernDist;
    }
    //cout<<"B : "<<posMeil<<" "<<distMeil<<endl;
    decompo(distMeil,9);
}

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
    nbSom=N;
    nbAre=B;
    deb=S;
    fin=T;
    prix=D;
    for (int i=0;i<nbAre;i++) {
        adja[deb[i]].push_back({fin[i],prix[i]});
        adja[fin[i]].push_back({deb[i],prix[i]});
    }
    for (int i=0;i<nbSom;i++) {
        sort(adja[i].begin(),adja[i].end(),[](pair<int,int> a,pair<int,int> b) {
            if (a.second>b.second) {
                return true;
            }
            return false;
        });
    }
    dist.push_back(0);
    for (int i=1;i<nbSom;i++) {
        dist.push_back(-1);
    }
    calcMeil();
}

void ReceiveB(bool x) {
    if (recevDist==0) {
        temp+=transfo(x)*(1<<numAppel);
        numAppel++;
        if (numAppel==9) {
            int distMeil=temp+dernDist;
            dernDist=distMeil;
            temp=0;
            numAppel=0;
            if (distMeil==propDist) {
                dist[propPos]=propDist;
                decompo(propPos,11);
                calcMeil();
            }
            else {
                recevDist=1;
            }
            //cout<<posMeil<<" "<<distMeil<<endl;
        }
    }
    else {
        temp+=transfo(x)*(1<<numAppel);
        numAppel++;
        if (numAppel==11) {
            dist[temp]=dernDist;
            numAppel=0;
            temp=0;
            recevDist=0;
            calcMeil();
        }
    }
}

• 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