Submission #1222670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222670		salmon	Two Transportations (JOI19_transportations)	C++20	0 / 100	155 ms	1168 KiB

Azer

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

namespace {

int N;
int lef;
bool used[2100];
int d[2100];
int cont = 0;
int big = 0;
int it = 0;
int v = 0;
int inf = 1e9;
vector<pair<int,int>> adjlst[2100];

void pack(int val, int n){
	for(int i = 0; i < n; i++){
		SendA((val&(1<<i))>0);
	}
	//printf("A %d\n",n);
}

}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
	::N = N;
	
	lef = N;

	for(int i = 0; i < A; i++){
		adjlst[U[i]].push_back({V[i],C[i]});
		adjlst[V[i]].push_back({U[i],C[i]});
	}

	for(int i = 0; i < N; i++){
		used[i] = false;
		d[i] = inf;
	}

	d[0] = 0;
	big = 0;

	for(pair<int,int> ii1 : adjlst[0]){
		d[ii1.first] = min(d[ii1.first],0 + ii1.second);
	}
	
	used[0] = true;
	lef--;
	
	int num = big + 501;
	for(int i = 0; i < N; i++) if(!used[i]) num = min(num,d[i]);
	
	pack(num - big,9);
	
	for(int i = 1; i <= 11; i++){
		if(lef+1 < (1<<i)){
			pack(0,i);
			break;
		}
	}
}

void ReceiveA(bool x) {
	if(cont == 0) if(!x) cont = 20;
	
	if(cont > 0 && cont < 12){
		 if(x) it += (1<<(cont-1));
	}
	else if(cont > 0){
		if(x) v += (1<<(cont-12));
	}
	
	if(cont == 20){
		/*printf("\nA\n");
		for(int i = 0; i < N; i++) printf("%d ",used[i]);
		printf("\n");
		for(int i = 0; i < N; i++) printf("%d ",d[i]);
		printf("\n");*/
				
		bool die = true;
		for(int i = 0; i < N; i++) die &= used[i];
		if(die) return;
		
		pair<int,int> ii = {inf,-1};
		for(int i = 0; i < N; i++){
			if(!used[i]) ii = min(ii,{d[i],i});
		}
		
		bool tell = true;
		//printf("%d %d %d\n",it,big,v+big);
		if(!(v == 0 && it == 0) && ii.first > v + big){
			ii = {v + big, it};
			tell = false;
		}
		
		d[ii.second] = ii.first;
		big = ii.first;
		
		int g = ii.second;
		for(pair<int,int> ii1 : adjlst[g]){
			d[ii1.first] = min(d[ii1.first],d[g] + ii1.second);
		}
		used[g] = true;
		lef--;
		
		int num = big + 501;
		for(int i = 0; i < N; i++) if(!used[i]) num = min(num,d[i]);
		pack(num - big,9);
		
		if(tell){
			vector<int> v;
			for(int i = 0; i < N; i++){
				if(!used[i] || i == g) v.push_back(i);
			}

			g = lower_bound(v.begin(),v.end(),g) - v.begin();

			for(int i = 1; i <= 11; i++){
				if(lef+2 < (1<<i)){
					pack(g,i);
					break;
				}
			}
		}
		
		cont = 0;
		it = 0;
		v = 0;
		
		/*printf("\nA\n");
		for(int i = 0; i < N; i++) printf("%d ",used[i]);
		printf("\n");
		for(int i = 0; i < N; i++) printf("%d ",d[i]);
		printf("\n");*/
		return;
	}
	++cont;
}

std::vector<int> Answer() {
  std::vector<int> ans(N);
  for (int k = 0; k < N; ++k) {
    ans[k] = d[k];
  }
  return ans;
}

Baijan

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

namespace {

int N;
bool used[2100];
int d[2100];
int lef;
int cont = 0;
int big = 0;
int it = 0;
int v = 0;
int inf = 1e9;
vector<pair<int,int>> adjlst[2100];
bool pastuse;
int pastv;

void pack(int val, int n){
	for(int i = 0; i < n; i++){
		SendB((val&(1<<i))>0);
	}
}



}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
	::N = N;
	
	lef = N;
	
	for(int i = 0; i < B; i++){
		adjlst[S[i]].push_back({T[i],D[i]});
		adjlst[T[i]].push_back({S[i],D[i]});
	}
	
	for(int i = 0; i < N; i++){
		used[i] = false;
		d[i] = inf;
	}

	pastuse = false;
	pastv = 0;
}

void ReceiveB(bool y) {
	//cerr << it << endl;
	//printf("%d ",y);
	if(cont < 9){
		if(y) v += (1<<cont);
	}
	
	if(cont > 8 && lef>=(1<<(cont-9)) && !pastuse){
		if(y) it += (1<<(cont-9));
	}
	
	if(cont > 8 && lef < (1<<(cont-8))){
		cont = 19;
	}
	
	
	if((cont == 8 && pastuse) || cont == 19){
		/*printf("\nB\n");
		for(int i = 0; i < N; i++) printf("%d ",used[i]);
		printf("\n");
		for(int i = 0; i < N; i++) printf("%d ",d[i]);
		printf("\n");*/

		if(!pastuse){
			cerr << endl << "it: "<< it << endl;
			vector<int> v;
			for(int i = 0 ; i < N; i++){
				if(!used[i]) v.push_back(i);
			}
			
			it = v[it];
			
			d[it] = pastv + big;
			used[it] = true;
			lef--;
			big = pastv + big;
			

			int g = it;
			for(pair<int,int> ii1 : adjlst[g]){
				d[ii1.first] = min(d[ii1.first],big + ii1.second);
			}
		}
		
		bool die = true;
		for(int i = 0; i < N; i++) die &= used[i];
		if(die) return;

		pair<int,int> ii = {inf,-1};
		for(int i = 0; i < N; i++){
			if(!used[i]) ii = min(ii,{d[i],i});
		} 
		//printf("f: %d\n",v+big);
		if(ii.first < v + big){
			pastuse = true;
			
			SendB(true);
			
			d[ii.second] = ii.first;
			used[ii.second] = true;
			lef--;
			
			pack(ii.second,11);
			pack(ii.first - big,9);
			
			big = ii.first;
			
			int g = ii.second;
			for(pair<int,int> ii1 : adjlst[g]){
				d[ii1.first] = min(d[ii1.first],big + ii1.second);
			}
		}
		else{
			//printf("work\n");
			pastuse = false;
			pastv = v;
			
			SendB(false);
		}
		
		cont = 0;
		it = 0;
		v = 0;

		/*printf("\nB\n");
		for(int i = 0; i < N; i++) printf("%d ",used[i]);
		printf("\n");
		for(int i = 0; i < N; i++) printf("%d ",d[i]);
		printf("\n");*/
		return;
	}
	
	cont++;
}

• 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