Submission #263608

#	Time	Username	Problem	Language	Result	Execution time	Memory
263608		patrikpavic2	Two Transportations (JOI19_transportations)	C++17	100 / 100	1788 ms	85656 KiB

Azer

#include "Azer.h"
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstdio>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef pair < int, int > pii;

namespace {

const int N = 2005;

int n;
vector < pii > v[N];
int dis[N], mks, bio[N];
int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
pii tmp; int cv, brj;

void obradi(int x){
	mks = max(mks, dis[x]);
	bio[x] = 1; // printf("A: obradujem %d\n", x);
	for(pii nxt : v[x]){
		if(dis[nxt.X] == -1 || dis[x] + nxt.Y < dis[nxt.X])
			dis[nxt.X] = dis[x] + nxt.Y;
	}
}

pii nadi_najblizeg(){
	int bst = 0, dod = mks + 501;
	for(int i = 0;i < n;i++){
		if(bio[i] || dis[i] == -1) continue;
		if(!bst || dis[i] < dod)
			bst = i, dod = dis[i];
	}
	tko = !!((cnt * (mks + n)) & 8);
	return {bst, dod - mks};
}

void posalji_broj(int x, int ln){
	//printf("A: saljem %d u %d\n", x, ln);
	for(int i = ln - 1;i >= 0;i--)
		SendA(!!(x & (1 << i)));
}

void korak(){
	tmp = nadi_najblizeg();
	cv = tmp.X, brj = tmp.Y;
	//printf("A: radim korak tko = %d\n", tko);
	//printf("A : cv = %d brj = %d\n", cv, brj);
	if(tko){
		sto = 1; jos = 1; ret = 0;
		posalji_broj(brj, 9);
	}
	else{
		sto = 4; jos = 9; ret = 0;
	}
}

} 

void InitA(int n, int a, vi U, vi V, vi C) {
	::n = n; 
	for(int i = 0;i < a;i++){
		v[U[i]].PB({V[i], C[i]});
		v[V[i]].PB({U[i], C[i]});
	}
	for(int i = 0; i < n;i++)
		dis[i] = -1;
	dis[0] = 0; cnt++; obradi(0);
	if(n != 1)
		SendA(0);
	Answer();
}



void ReceiveA(bool x) {
	if(sto == 0) {
		korak(); return;
	}
	ret = 2 * ret + x; jos--;
	//printf("B: jos = %d ret = %d sto = %d\n", jos, ret, sto);
	if(jos != 0) return;
	if(sto == 1){
		if(ret){
			//printf("tu sam\n");
			jos = 9;
			sto = 2;
			ret = 0;
		}
		else{
			posalji_broj(cv, 11);
			dis[cv] = mks + brj;
			obradi(cv);
			if((++cnt) != n)
				korak();
		}
	}
	else if(sto == 2){
		brj = ret; ret = 0;
		jos = 11; 
		sto = 3;
	}
	else if(sto == 3){
		cv = ret; ret = 0;
		dis[cv] = mks + brj;
		obradi(cv);
		if((++cnt) != n)
			korak();
	}
	else if(sto == 4){
		brj2 = ret; ret = 0;
		if(brj2 <= brj){
			brj = brj2;
			sto = 5; jos = 11; ret = 0;
			posalji_broj(0, 1);
		}
		else{
			posalji_broj(1, 1);
			posalji_broj(brj, 9);
			posalji_broj(cv, 11);
			dis[cv] = mks + brj;
			obradi(cv);
			if((++cnt) != n)
				korak();
		}
	}
	else if(sto == 5){
		cv = ret; ret = 0;
		dis[cv] = mks + brj;
		obradi(cv);
		if((++cnt) != n)
			korak();
	}
}

vi Answer() {
  vi ans(n);
  for (int k = 0; k < n; ++k) {
    ans[k] = dis[k];
  }
  return ans;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <queue>
#include <cstdlib>
#include <cstdio>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef pair < int, int > pii;

namespace {

const int N = 2005;

int n;
vector < pii > v[N];
int dis[N], mks, bio[N];
int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
pii tmp; int cv, brj;

void obradi(int x){
	mks = max(mks, dis[x]);
	bio[x] = 1; //printf("B: obradujem %d\n", x);
	for(pii nxt : v[x]){
		if(dis[nxt.X] == -1 || dis[x] + nxt.Y < dis[nxt.X])
			dis[nxt.X] = dis[x] + nxt.Y;
	}
}

pii nadi_najblizeg(){
	int bst = 0, dod = mks + 501; 
	for(int i = 0;i < n;i++){
		if(bio[i] || dis[i] == -1) 
			continue;
		if(!bst || dis[i] < dod)
			bst = i, dod = dis[i];
	}
	tko = !((cnt * (mks + n)) & 8);
	return {bst, dod - mks};
}

void posalji_broj(int x, int ln){
	//printf("B: saljem %d u %d\n", x, ln);
	for(int i = ln - 1;i >= 0;i--)
		SendB(!!(x & (1 << i)));
}

void korak(){
	tmp = nadi_najblizeg();
	cv = tmp.X, brj = tmp.Y;
	//printf("B: radim korak tko = %d\n", tko);
	//printf("B : cv = %d brj = %d\n", cv, brj);
	if(tko){
		sto = 1; jos = 1; ret = 0;
		posalji_broj(brj, 9);
	}
	else{
		sto = 4; jos = 9; ret = 0;
	}
} 

}

void InitB(int n, int a, vi U, vi V, vi C) {
	::n = n; 
	for(int i = 0;i < a;i++){
		v[U[i]].PB({V[i], C[i]});
		v[V[i]].PB({U[i], C[i]});
	}
	for(int i = 0; i < n;i++)
		dis[i] = -1;
	dis[0] = 0; cnt++; obradi(0);
	if(n != 1)
		SendB(0);
	
}



void ReceiveB(bool x) {
	if(sto == 0) {
		korak(); return;
	}
	ret = 2 * ret + x; jos--;
	//printf("B: jos = %d ret = %d sto = %d\n", jos, ret, sto);
	if(jos != 0) return;
	if(sto == 1){
		if(ret){
			//printf("tu sam\n");
			jos = 9;
			sto = 2;
			ret = 0;
		}
		else{
			posalji_broj(cv, 11);
			dis[cv] = mks + brj;
			obradi(cv);
			if((++cnt) != n)
				korak();
		}
	}
	else if(sto == 2){
		brj = ret; ret = 0;
		jos = 11; 
		sto = 3;
	}
	else if(sto == 3){
		cv = ret; ret = 0;
		dis[cv] = mks + brj;
		obradi(cv);
		if((++cnt) != n)
			korak();
	}
	else if(sto == 4){
		brj2 = ret; ret = 0;
		if(brj2 <= brj){
			brj = brj2;
			sto = 5; jos = 11; ret = 0;
			posalji_broj(0, 1);
		}
		else{
			posalji_broj(1, 1);
			posalji_broj(brj, 9);
			posalji_broj(cv, 11);
			dis[cv] = mks + brj;
			obradi(cv);
			if((++cnt) != n)
				korak();
		}
	}
	else if(sto == 5){
		cv = ret; ret = 0;
		dis[cv] = mks + brj;
		obradi(cv);
		if((++cnt) != n)
			korak();
	}
}

Compilation message (stderr)

Azer.cpp:23:14: warning: '{anonymous}::kolko' defined but not used [-Wunused-variable]
   23 | int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
      |              ^~~~~

Baijan.cpp:23:14: warning: '{anonymous}::kolko' defined but not used [-Wunused-variable]
   23 | int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 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