제출 #1252329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252329		trandangquang	Two Transportations (JOI19_transportations)	C++20	100 / 100	319 ms	48964 KiB

Azer

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

/**
    3 stage:
    - stage 1: send weight
    - stage 2: compare weight, if smaller -> send node, else wait
    - stage 3: mark (if weight is larger)

    do n stages
**/

const int N=2222;
const int INF=1e9;

int nA,eA,cntStageA,curStageA; bool visA[N];
vector<int> disA;
vector<pair<int,int>> adjA[N];

void stage1A();
void stage2A();
void stage3A();

void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){ /// input
    nA=n; eA=a;
    for(int i=0; i<a; ++i){
        adjA[u[i]].emplace_back(v[i],c[i]);
        adjA[v[i]].emplace_back(u[i],c[i]);
    }

    disA.resize(nA,INF);
    disA[0]=0;
    stage1A(); /// starting point
}

int cntrevA=0, revA=0, nxtdisA=0;
int curdisA=0, curverA=0;

void stage1A(){
    if(cntStageA==nA) return;
    ++cntStageA;

    int vdis=-1;
    for(int i=0; i<nA; ++i) if(!visA[i]){
        if(vdis==-1 || disA[vdis]>disA[i]){
            vdis=i;
        }
    }
    curverA=vdis; /// find the minimum distance from 0
    for(int i=8; i>=0; --i){
        if(disA[vdis]==INF) SendA(1);
        else SendA((disA[vdis]-curdisA)>>i&1);
    }
//    cout<<disA[vdis]-curdisA<<'\n';
    cntrevA=8, revA=0;
    curStageA=2;
}

void stage2A(){
    if(disA[curverA]-curdisA <= revA){
        for(int i=10; i>=0; --i){
            SendA(curverA>>i&1);
        }
        visA[curverA]=true;
        for(auto [i,w]:adjA[curverA]){
            disA[i]=min(disA[i],disA[curverA]+w);
        }
        curdisA=disA[curverA]; /// reupdate current min distance

        stage1A(); /// start again
    } else{
        nxtdisA=revA+curdisA; /// will take minimum from opponent's
        cntrevA=10, revA=0;
        curStageA=3;
    }
}

void stage3A(){
    curdisA=nxtdisA;
    disA[revA]=nxtdisA;
    visA[revA]=true;
    for(auto [i,w]:adjA[revA]){
        disA[i]=min(disA[i],disA[revA]+w);
    }
    stage1A();
}

void ReceiveA(bool x){
    if(x==1) revA|=(1<<cntrevA);
    --cntrevA;
    if(cntrevA==-1){
//        cout<<curStageA<<'\n';
        if(curStageA==2) stage2A();
        else if(curStageA==3) stage3A();
        else assert(0);
    }
}

vector<int> Answer(){
    return disA;
}

Baijan

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

const int N=2222;
const int INF=1e9;

int nB,eB,cntStageB,curStageB; bool visB[N];
vector<int> disB;
vector<pair<int,int>> adjB[N];

void stage1B();
void stage2B();
void stage3B();

void InitB(int n, int b, vector<int> s, vector<int> t, vector<int> d){
    nB=n,eB=b;
    for(int i=0; i<b; ++i){
        adjB[s[i]].emplace_back(t[i],d[i]);
        adjB[t[i]].emplace_back(s[i],d[i]);
    }

    disB.resize(nB,INF);
    disB[0]=0;
    stage1B();
}

int cntrevB=0, revB=0, nxtdisB=0;
int curdisB=0, curverB=0;

void stage1B(){
    if(cntStageB==nB) return;
    ++cntStageB;

    int vdis=-1;
    for(int i=0; i<nB; ++i) if(!visB[i]){
        if(vdis==-1 || disB[vdis]>disB[i]){
            vdis=i;
        }
    }
    curverB=vdis;
    for(int i=8; i>=0; --i){
        if(disB[vdis]==INF) SendB(1);
        else SendB((disB[vdis]-curdisB)>>i&1);
    }

    cntrevB=8, revB=0;
    curStageB=2;
}

void stage2B(){
//    cout<<disB[curverB]<<" "<<curdisB<<'\n';
    if(disB[curverB]-curdisB < revB){
        for(int i=10; i>=0; --i){
            SendB(curverB>>i&1);
//            cout<<(curverB>>i&1)<<'\n';
        }
        visB[curverB]=true;
        for(auto [i,w]:adjB[curverB]){
            disB[i]=min(disB[i],disB[curverB]+w);
        }
        curdisB=disB[curverB];

        stage1B();
    } else{
        nxtdisB=revB+curdisB;
        cntrevB=10, revB=0;
        curStageB=3;
    }
}

void stage3B(){
    curdisB=nxtdisB;
    disB[revB]=nxtdisB;
    visB[revB]=true;
    for(auto [i,w]:adjB[revB]){
        disB[i]=min(disB[i],disB[revB]+w);
    }
    stage1B();
}

void ReceiveB(bool x){
    if(x==1) revB|=(1<<cntrevB);
    --cntrevB;
    if(cntrevB==-1){
        if(curStageB==2) stage2B();
        else if(curStageB==3) stage3B();
        else assert(0);
    }
}

• 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