oj.uz

Submission #263605

# Submission time Handle Problem Language Result Execution time Memory
263605 2020-08-13T20:53:48 Z patrikpavic2 Two Transportations (JOI19_transportations) C++17
14 / 100
 3000 ms 35968 KB 
#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];
queue < bool > info;
int dis[N], mks;
int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
pii tmp; int cv, brj;

pii nadi_najblizeg(){
	int bst = 0, dod = 501; mks = 0;
	for(int i = 0;i < n;i++)
		if(dis[i] > mks) mks = dis[i];
	for(int i = 0;i < n;i++){
		if(dis[i] == -1) continue;
		for(pii nxt : v[i]){
			if(dis[nxt.X] != -1) continue;
			if(nxt.Y + dis[i] - mks < dod){
				dod = nxt.Y + dis[i] - mks;
				bst = nxt.X;
			}
		}
	}
	tko = !((cnt * (mks + n)) & 8);
	return {bst, dod};
}

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();
	//printf("A: radim korak tko = %d\n", tko);
	cv = tmp.X, brj = tmp.Y;
	//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++;
	if(n != 1)
		SendA(0);
	Answer();
}



void ReceiveA(bool x) {
	if(sto == 0) {
		korak(); return;
	}
	ret = 2 * ret + x; jos--;
	//printf("A: jos = %d ret = %d sto = %d\n", jos, ret, sto);
	if(jos != 0) return;
	if(sto == 1){
		if(ret){
			jos = 9;
			sto = 2;
			ret = 0;
		}
		else{
			posalji_broj(cv, 11);
			dis[cv] = mks + brj;
			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;
		if((++cnt) != n)
			korak();
	}
	else if(sto == 4){
		brj2 = ret; ret = 0;
		if(brj2 <= brj){
			posalji_broj(0, 1);
			brj = brj2;
			sto = 5; jos = 11;
		}
		else{
			posalji_broj(1, 1);
			posalji_broj(brj, 9);
			posalji_broj(cv, 11);
			dis[cv] = mks + brj;
			if((++cnt) != n)
				korak();
		}
	}
	else if(sto == 5){
		cv = ret; ret = 0;
		dis[cv] = mks + brj;
		if((++cnt) != n)
			korak();
	}
}

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









#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];
queue < bool > info;
int dis[N], mks;
int sto = 0, kolko = 0, jos = 0, ret = 0, brj2, cnt = 0, tko = 0;
pii tmp; int cv, brj;

pii nadi_najblizeg(){
	int bst = 0, dod = 501; mks = 0;
	for(int i = 0;i < n;i++)
		if(dis[i] > mks) mks = dis[i];
	for(int i = 0;i < n;i++){
		if(dis[i] == -1) continue;
		for(pii nxt : v[i]){
			if(dis[nxt.X] != -1) continue;
			if(nxt.Y + dis[i] - mks < dod){
				dod = nxt.Y + dis[i] - mks;
				bst = nxt.X;
			}
		}
	}
	tko = !!((cnt * (mks + n)) & 8);
	return {bst, dod};
}

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();
	//printf("B: radim korak tko = %d\n", tko);
	cv = tmp.X, brj = tmp.Y;
	//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++;
	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;
			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;
		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;
			if((++cnt) != n)
				korak();
		}
	}
	else if(sto == 5){
		cv = ret; ret = 0;
		dis[cv] = mks + brj;
		if((++cnt) != n)
			korak();
	}
}

Compilation message

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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 2016 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 976 ms 1568 KB Output is correct
4 Correct 2707 ms 20192 KB Output is correct
5 Correct 60 ms 1552 KB Output is correct
6 Correct 1556 ms 4352 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 953 ms 1536 KB Output is correct
3 Correct 896 ms 1824 KB Output is correct
4 Execution timed out 3000 ms 27504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 1792 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 912 ms 1824 KB Output is correct
4 Correct 787 ms 1856 KB Output is correct
5 Correct 978 ms 1536 KB Output is correct
6 Correct 864 ms 1568 KB Output is correct
7 Correct 966 ms 1624 KB Output is correct
8 Correct 876 ms 1672 KB Output is correct
9 Correct 1178 ms 1536 KB Output is correct
10 Correct 1042 ms 1600 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 1536 KB Output is correct
2 Correct 374 ms 1536 KB Output is correct
3 Correct 1726 ms 23800 KB Output is correct
4 Correct 410 ms 1536 KB Output is correct
5 Correct 1394 ms 17472 KB Output is correct
6 Correct 542 ms 1536 KB Output is correct
7 Correct 470 ms 1536 KB Output is correct
8 Correct 356 ms 1536 KB Output is correct
9 Execution timed out 3000 ms 35968 KB
10 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 1536 KB Output is correct
2 Correct 374 ms 1536 KB Output is correct
3 Correct 1726 ms 23800 KB Output is correct
4 Correct 410 ms 1536 KB Output is correct
5 Correct 1394 ms 17472 KB Output is correct
6 Correct 542 ms 1536 KB Output is correct
7 Correct 470 ms 1536 KB Output is correct
8 Correct 356 ms 1536 KB Output is correct
9 Execution timed out 3000 ms 35968 KB
10 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 1536 KB Output is correct
2 Correct 374 ms 1536 KB Output is correct
3 Correct 1726 ms 23800 KB Output is correct
4 Correct 410 ms 1536 KB Output is correct
5 Correct 1394 ms 17472 KB Output is correct
6 Correct 542 ms 1536 KB Output is correct
7 Correct 470 ms 1536 KB Output is correct
8 Correct 356 ms 1536 KB Output is correct
9 Execution timed out 3000 ms 35968 KB
10 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 2016 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct
3 Correct 976 ms 1568 KB Output is correct
4 Correct 2707 ms 20192 KB Output is correct
5 Correct 60 ms 1552 KB Output is correct
6 Correct 1556 ms 4352 KB Output is correct
7 Correct 2 ms 1280 KB Output is correct
8 Correct 953 ms 1536 KB Output is correct
9 Correct 896 ms 1824 KB Output is correct
10 Execution timed out 3000 ms 27504 KB Time limit exceeded
11 Halted 0 ms 0 KB -