Submission #112269

#	Time	Username	Problem	Language	Result	Execution time	Memory
112269		gs14004	Two Transportations (JOI19_transportations)	C++17	100 / 100	2106 ms	85344 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
using pi = pair<int, int>;

namespace {
	vector<pi> gph[MAXN];
	int dist[MAXN];
	bool vis[MAXN];
	bool firstSkip = 1;
	int n, recValue1, recValue2, curMode;	
	void sendValue(int x, int b){
		for(int i=b-1; i>=0; i--){
			SendA((x >> i) & 1);
		}
	}
	void relax(int v){	
//		printf("A relaxed %d = %d\n", v, dist[v]);
		vis[v] = 1;
		for(auto &i : gph[v]){
			dist[i.second] = min(dist[i.second], i.first + dist[v]);
		}
	}
	int getMax(){
		int ret = 0;
		for(int i=0; i<n; i++){
			if(vis[i]) ret = max(ret, dist[i]);
		}
		return ret;
	}
}  // namespace


void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
		std::vector<int> C) {
	n = N;
	for(int i=0; i<A; i++){
		gph[U[i]].emplace_back(C[i], V[i]);
		gph[V[i]].emplace_back(C[i], U[i]);
	}
	memset(dist, 0x3f, sizeof(dist));
	dist[0] = 0;
}

void ReceiveA(bool x) {
	if(curMode == 0){
		curMode = 69;
		if(count(vis, vis + n, 1) == n) return;
		int cur = 1048575, pos = -1;
		for(int i=0; i<n; i++){
			if(!vis[i] && dist[i] < cur){
				cur = dist[i];
				pos = i;
			}
		}
		cur -= getMax();
		cur = min(cur, 511);
		sendValue(cur, 9 - firstSkip);
		firstSkip = 0;
		return;
	}
	if(curMode >= 69){
		if(curMode < 80){
			recValue1 = recValue1 * 2 + x;
		}
		else{
			recValue2 = recValue2 * 2 + x;
		}
		curMode++;
		if(curMode == 77 && recValue1 == 255){
			int cur = 1048575, pos = -1;
			for(int i=0; i<n; i++){
				if(!vis[i] && dist[i] < cur){
					cur = dist[i];
					pos = i;
				}
			}
			relax(pos);
			sendValue(pos, 11);
			curMode = 0;
			recValue1 = recValue2 = 0;
		}
		if(curMode == 89){
			dist[recValue1] = min(dist[recValue1], recValue2 + getMax());
			relax(recValue1);
			recValue1 = recValue2 = 0;
			curMode = 0;
			ReceiveA(0);
		}
	}
}

vector<int> Answer(){
	vector<int> v(dist, dist + n);
	return v;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
using pi = pair<int, int>;

namespace {
	vector<pi> gph[MAXN];
	int dist[MAXN];
	bool vis[MAXN];
	int n, recValue, recValue2, curMode;
	bool firstSkip = 1;
	void sendValue(int x, int b){
		for(int i=b-1; i>=0; i--){
			SendB((x >> i) & 1);
		}
	}
	void relax(int v){
	//	printf("B relaxed %d = %d\n", v, dist[v]);
		vis[v] = 1;
		for(auto &i : gph[v]){
			dist[i.second] = min(dist[i.second], i.first + dist[v]);
		}
	}
	int getMax(){
		int ret = 0;
		for(int i=0; i<n; i++){
			if(vis[i]) ret = max(ret, dist[i]);
		}
		return ret;
	}
}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
		std::vector<int> D) {
	n = N;
	for(int i=0; i<B; i++){
		gph[S[i]].emplace_back(D[i], T[i]);
		gph[T[i]].emplace_back(D[i], S[i]);
	}
	memset(dist, 0x3f, sizeof(dist));
	dist[0] = 0;
	SendB(0);
}

void ReceiveB(bool y) {
	if(curMode < 9 - firstSkip){
		curMode++;
		recValue = recValue * 2 + y;
	}
	if(curMode < 9 - firstSkip) return;
	if(curMode > 999){
		curMode++;
		recValue2 = recValue2 * 2 + y;
		if(curMode >= 1011){
			dist[recValue2] = min(dist[recValue2], recValue + getMax());
			relax(recValue2);
			recValue = recValue2 = 0;
			curMode = 0;
			SendB(0);
		}
		return;
	}
	firstSkip = 0;
	int cur = 1048575, pos = -1;
	for(int i=0; i<n; i++){
		if(!vis[i] && dist[i] < cur){
			cur = dist[i];
			pos = i;
		}
	}
	cur -= getMax();
	int another_dist = recValue;
	if(cur > another_dist){
		sendValue(255, 8);
		curMode = 1000;
		// beg A to answer the vertex number
	}
	else{
		relax(pos);
		curMode = 0;
		recValue = recValue2 = 0;
		sendValue(pos, 11);
		sendValue(cur, 9);
		// tell A that vertex number with its distance
	}
}

Compilation message (stderr)

Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:50:22: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   int cur = 1048575, pos = -1;
                      ^~~

• 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