Submission #240123

#	Time	Username	Problem	Language	Result	Execution time	Memory
240123		kshitij_sodani	Two Transportations (JOI19_transportations)	C++17	100 / 100	1849 ms	86040 KiB

Azer

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#include "Azer.h"
 
 
 
vector<pair<int,int>> adj[2001];
int dist[2001];
int vis[2001];
int num=0;
int cur=0;
int st=0;
int last=0;
pair<int,int> best;
int num2=0;
int cur2=0;
int n;
vector<int> Answer(){
	vector<int> ans2;
	for(int i=0;i<n;i++){
		ans2.pb(dist[i]);
	}
	return ans2;
 
}
void ReceiveA(bool x){
	if(st==0){
		if(x){
			num+=(1<<cur);
		}
		cur+=1;
		if(cur==9){
			cur=0;
			st=1;
		}
		else{
			return;
		}
		//cout<<cur<<"<"<<num<<endl;
	}
	if(st==1){
		for(auto j:adj[last]){
			if(dist[j.a]==-1 or dist[j.a]>dist[last]+j.b){
				dist[j.a]=dist[last]+j.b;
			}
		}
		best={-1,-1};
		for(int i=0;i<n;i++){
		//	//cout<<i<<":::"<<dist[i]<<endl;
			if(vis[i]==0 and dist[i]!=-1){
				if(best.a==-1){
					best={dist[i],i};
				}
				else{
					if(dist[i]<best.a){
						best={dist[i],i};
					}
				}
			}
		}
		if(best.a==-1){
			best.a=dist[last]+511;
		}
		//cout<<best.a<<"::"<<best.b<<"::"<<num<<endl;
	/*	if(num==0){
			SendA(0);
			st=3;
		}
		else if(best.a==-1){
			SendA(1);
			st=2;
		}*/
		if(best.a<num){
		//	SendA(0);
		/*	for(int i=0;i<9;i++){
				if((1<<i)&(best.a-dist[last])){
					SendA(1);
				}
				else{
					SendA(0);
				}
			}*/
			st=3;
		}
		else{
			for(int i=0;i<9;i++){
				SendA(1);
			}
			//SendA(1);
			st=2;
		}
		//cout<<st<<"....."<<endl;
		if(st==2){
			return;
		}
	}
	if(st==2){
		if(x){
			num2+=(1<<cur2);
		}
		cur2+=1;
		//cout<<cur2<<";;;;;;;;;;;;;;;"<<endl;
		if(cur2==11){
			last=num2;
			//cout<<num2<<"//"<<endl;
			vis[last]=1;
			dist[last]=num;
		}
		else{
			return;
		}		
	}
	if(st==3){
		dist[best.b]=best.a;
		vis[best.b]=1;
		if(dist[last]>best.a){
			while(true){
				continue;
			}
		}
		for(int i=0;i<9;i++){
			if((1<<i)&(best.a-dist[last])){
				SendA(1);
			}
			else{
				SendA(0);
			}
		}
		for(int i=0;i<11;i++){
			if((1<<i)&best.b){
				SendA(1);
			}
			else{
				SendA(0);
			}
		}
		last=best.b;
 
	}
	//cout<<last<<','<<dist[last]<<endl;
	st=0;
	num=dist[last];
	num2=0;
	cur2=0;
	cur=0;
/*	int kk=0;
	for(int i=0;i<n;i++){
		if(vis[i]==0){
			kk=1;
		}
	}
	if(kk){
		SendA(0);
	}*/
}
void InitA(int nn,int m,vector<int> aa,vector<int> bb,vector<int> cc){
	n=nn;
	for(int i=0;i<m;i++){
		adj[aa[i]].pb({bb[i],cc[i]});
		adj[bb[i]].pb({aa[i],cc[i]});
	}
	for(int i=1;i<n;i++){
		dist[i]=-1;
	}
	vis[0]=1;
	//SendA(0);
}
 
 
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	return 0;
}*/

Baijan

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "Baijan.h"
 
vector<pair<int,int>> adj2[2001];
int dist2[2001];
int st2=0;
int last2=0;
int vis2[2001];
pair<int,int> best2;
int ne;
int cur3=0;
int cur4=0;
int num3=0;
int num4=0;
void ReceiveB(bool x){
	if(st2==0){
		for(auto j:adj2[last2]){
			if(dist2[j.a]==-1 or dist2[j.a]>dist2[last2]+j.b){
				dist2[j.a]=dist2[last2]+j.b;
			}
		}
		best2={-1,-1};
		for(int i=0;i<ne;i++){
			if(vis2[i]==0 and dist2[i]!=-1){
				if(best2.a==-1){
					best2={dist2[i],i};
				}
				else{
					if(dist2[i]<best2.a){
						best2={dist2[i],i};
					}
				}
			}
		}
		if(best2.a==-1){
			best2.a=dist2[last2]+511;
		}
		//cout<<best2.a<<"::"<<best2.b<<endl;
	//	best2.a=max(best2.a,0);
		if(best2.a<dist2[last2]){
			while(true){
				continue;
			}
		}
		for(int i=0;i<9;i++){
			if((1<<i)&(best2.a-dist2[last2])){
				SendB(1);
			}
			else{
				SendB(0);
			}
		}
		st2=3;
		return;
	}
/*	if(st2==1){
		if(x){
			st2=2;
		}
		else{
			st2=3;
			return;
		}
	}*/
	if(st2==2){
		//cout<<1111<<endl;
		
	}
	if(st2==3){
		if(cur3==0){
			num3+=(dist2[last2]);
		}
		if(cur3<9){
			if(x){
				num3+=(1<<cur3);
			}
			cur3++;
			if(num3-dist2[last2]==511){
				st2=0;
				dist2[best2.b]=best2.a;
				vis2[best2.b]=1;
				last2=best2.b;
			//	cout<<111<<endl;
				for(int i=0;i<11;i++){
					if((1<<i)&best2.b){
						SendB(1);
					}
					else{
						SendB(0);
					}
				}

			}
			else{
				return;
			}
		}
		else{
			if(x){
				num4+=(1<<cur4);
			}
			cur4++;
			if(cur4==11){
				//cout<<20<<endl;
 
				//cout<<num4<<",,"<<num3<<endl;
 
				dist2[num4]=num3;
				vis2[num4]=1;
				last2=num4;
				
			}
			else{
				return;
			}
		}
	}
//	//cout<<last2<<"<<<>>>>"<<endl;
	num3=0;
	num4=0;
	cur3=0;
	cur4=0;
	st2=0;
	int kk=0;
	for(int i=0;i<ne;i++){
		if(vis2[i]==0){
			kk=1;
		}
	}
	if(kk){
		ReceiveB(0);
	}
 
 
}
void InitB(int nn,int m,vector<int> aa,vector<int> bb,vector<int> cc){
	ne=nn;
	for(int i=0;i<m;i++){
		adj2[aa[i]].pb({bb[i],cc[i]});
		adj2[bb[i]].pb({aa[i],cc[i]});
	}
	for(int i=1;i<ne;i++){
		dist2[i]=-1;
	}
	vis2[0]=1;
	ReceiveB(0);
}
 
 
/*int main(){
	ios_base::sync_with_st2dio(false);
	cin.tie(NULL);
 
	return 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