Submission #410499

#	Time	Username	Problem	Language	Result	Execution time	Memory
410499		wittydolphin	Two Transportations (JOI19_transportations)	C++14	6 / 100	718 ms	36928 KiB

Azer

#include <iostream>
#include <vector>
#include <bitset>
#include "Azer.h"

using namespace std;
int COSTA=0;
int NN;
const int INFA=100000000;
int receivedA=0;
int counterA=0;
int distBAI=0;
vector <int> visitedA(2000,0);
vector <int> costsA(2000,INFA);
int gridA[2000][2000];
vector <int> Ans;
vector <int> Answer(){
	for(int i=0;i<NN;i++){
		Ans.push_back(costsA[i]);
	}
	return Ans;
}
void ReceiveA(bool x){
	if(x){
		receivedA*=2;
		receivedA+=1;
	}else{
		receivedA*=2;
	}
	counterA++;
	if(counterA==9){
		int MiN_index=-1; 
		int MiN=2*INFA;
		for(int j=0;j<NN;j++){
			if(visitedA[j]==0&&MiN>costsA[j]){
				MiN=costsA[j];
				MiN_index=j;
			}
		}
		if(MiN_index==-1){return;}
		distBAI=receivedA;
		receivedA=0;
		// cout<<distBAI<<' '<<MiN-COSTA<<endl;
		if(MiN-COSTA>distBAI){//Bus is better
	        // cout<<distBAI<<"BAI"<<endl;
			COSTA+=distBAI;
			for(int k=0;k<9;k++){
				SendA(1);
			}//this is 511
		}else{
			int distAZE=MiN-COSTA;//our one is better
	        // cout<<distAZE<<"AZE"<<endl;
			COSTA+=distAZE;
			bitset <9> sender(distAZE);
			for(int k=0;k<9;k++){
				SendA(sender[8-k]);
			}
			bitset <11> place(MiN_index);
			for(int k=0;k<11;k++){
				SendA(place[10-k]);
			}
			receivedA=MiN_index;
			visitedA[MiN_index]=1;
			counterA=20;
		}
	}
	if(counterA==20){//Baijan was better
		//received is now place
		costsA[receivedA]=COSTA;
		visitedA[receivedA]=1;
		for(int j=0;j<NN;j++){
			if(costsA[j]>COSTA+gridA[receivedA][j]){
				costsA[j]=COSTA+gridA[receivedA][j];//renew costsAs
			}
		}
		receivedA=0;
		counterA=0;
	}
}
void InitA(int M, int A, vector <int> U,vector <int> V,vector <int> C){
	NN=M;
	costsA[0]=0;
	visitedA[0]=1;
	for(int i=0;i<NN;i++){
		for(int j=0;j<NN;j++){
			gridA[i][j]=INFA;
		}
	}
	for(int i=0;i<A;i++){
		gridA[U[i]][V[i]]=C[i];
		gridA[V[i]][U[i]]=C[i];
	}
	for(int j=1;j<NN;j++){
		costsA[j]=gridA[0][j];//renew costsAs
	}
}

Baijan

#include <iostream>
#include <vector>
#include <bitset>
#include "Baijan.h"


using namespace std;
int COST=0;
int N;
const int INF=100000000;
vector <int> visited(2000,0);
vector <int> costs(2000,INF);
int distAz,distBa,MiN,MiN_index;
int received=0;
int counter=0;
int grid[2000][2000];
void ReceiveB(bool y){
	if(y){
		received*=2;
		received+=1;
	}else{
		received*=2;
	}
	counter++;
	if(counter==9){
		distAz=received;
		received=0;
		if(distAz==511){///Baij is better
	        counter=20;
	        bitset <11> place(MiN_index);
	        for(int k=0;k<11;k++){
	            SendB(place[10-k]);
	        }
	        COST+=distBa;
	        received=MiN_index;
	    }else{
	        COST+=distAz;//wait till they send index  
	    }
	}
	if(counter==20){//received is 
    	costs[received]=COST;
        visited[received]=1;
        for(int j=0;j<N;j++){
            if(costs[j]>COST+grid[received][j]){
                costs[j]=COST+grid[received][j];//renew costss
            }
        }
        counter=0;
        received=0;
        MiN_index=-1;
	    MiN=2*INF;
	    for(int j=0;j<N;j++){
	        if(visited[j]==0&&MiN>costs[j]){
	            MiN=costs[j];
	            MiN_index=j;
	        }
	    }
	    if(MiN_index==-1){return;}
		distBa=MiN-COST;
		if(distBa>500){
			distBa=511;
		}
		bitset <9> sender(distBa);
		for(int k=0;k<9;k++){
		    SendB(sender[8-k]);
		}
    }
}
void InitB(int M, int A, vector <int> S,vector <int> T,vector <int> D){
	N=M;
	costs[0]=0;
	visited[0]=1;
	for(int i=0;i<N;i++){
	    for(int j=0;j<N;j++){
	      grid[i][j]=INF;
	    }
	}
	for(int i=0;i<A;i++){
	    grid[S[i]][T[i]]=D[i];
	    grid[T[i]][S[i]]=D[i];
	}
	for(int j=1;j<N;j++){
        costs[j]=grid[0][j];//renew costss
    }
	MiN_index=-1;
    MiN=INF;
    for(int j=0;j<N;j++){
        if(visited[j]==0&&MiN>costs[j]){
            MiN=costs[j];
            MiN_index=j;
        }
    }
    if(MiN_index==-1){return;}
    distBa=MiN-COST;
    if(distBa>500){
		distBa=511;
	}
	bitset <9> sender(distBa);
	for(int k=0;k<9;k++){
	    SendB(sender[8-k]);
	}
}

• Subtask 1: 6 / 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