Submission #683623

#	Time	Username	Problem	Language	Result	Execution time	Memory
683623		MilosMilutinovic	Two Transportations (JOI19_transportations)	C++14	100 / 100	816 ms	48900 KiB

Azer

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

namespace {
const int N=2020;
const int inf=(int)1e9;
int n,dist[N],x,d,wei,num,cnt,st,mx;
vector<pair<int,int>> g[N];
bool act[N];

void init() {
	for (int i=0;i<N;i++) dist[i]=inf;
	dist[0]=0;
	act[0]=1;
	cnt=0;
	num=0;
	st=1;
}
void send(int v) {
	mx=0;
	for (int i=0;i<n;i++) if (act[i]) mx=max(mx,dist[i]);
	d=dist[v]-mx;
	d=min(d,511);
	for (int i=8;i>=0;i--) SendA(d>>i&1);
}
void update(int v) {
//	printf("A updatuje %d\n",v);
	for (auto&e : g[v]) {
		int u=e.first;
		int w=e.second;
		dist[u]=min(dist[u],dist[v]+w);
	}
	x=-1;
	for (int i=0;i<n;i++) {
		if (!act[i]&&(x==-1||dist[i]<dist[x])) {
			x=i;
		}
	}
	if (x!=-1) send(x);
}

}

void InitA(int N,int A,vector<int> U,vector<int> V,vector<int> C) {
	::n=N;
	for (int i=0;i<A;i++) {
		g[U[i]].push_back({V[i],C[i]});
		g[V[i]].push_back({U[i],C[i]});
	}
	init();
	update(0);
}

void ReceiveA(bool y) {
	num=num*2+y;
	cnt++;
	if (st==1&&cnt==9) {
//		printf("A recieved %d\n",num);
		cnt=0;
		if (num>=d) {
			for (int i=10;i>=0;i--) SendA(x>>i&1);
			act[x]=1;
			update(x);
			num=0;
			st=1;
		} else {
			wei=num;
			cnt=0;
			num=0;
			st=2;
		}
	}
	if (st==2&&cnt==11) {
		cnt=0;
		dist[num]=mx+wei;
		act[num]=1;
		update(num);
		num=0;
		st=1;
	}
}

vector<int> Answer() {
	vector<int> ans;
	for (int i=0;i<n;i++) ans.push_back(dist[i]);
	return ans;
}

/*
4 3 4
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7
*/

Baijan

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

namespace {
const int N=2020;
const int inf=(int)1e9;
int n,dist[N],x,d,wei,num,cnt,st,mx;
vector<pair<int,int>> g[N];
bool act[N];

void init() {
	for (int i=0;i<N;i++) dist[i]=inf;
	dist[0]=0;
	act[0]=1;
	cnt=0;
	num=0;
	st=1;
}
void send(int v) {
	mx=0;
	for (int i=0;i<n;i++) if (act[i]) mx=max(mx,dist[i]);
	d=dist[v]-mx;
	d=min(d,511);
	for (int i=8;i>=0;i--) SendB(d>>i&1);
}
void update(int v) {
//	printf("B updatuje %d\n",v);
	for (auto&e : g[v]) {
		int u=e.first;
		int w=e.second;
		dist[u]=min(dist[u],dist[v]+w);
	}
	x=-1;
	for (int i=0;i<n;i++) {
		if (!act[i]&&(x==-1||dist[i]<dist[x])) {
			x=i;
		}
	}
//	printf("B je naso x=%d\n",x);
	if (x!=-1) send(x);
}

}

void InitB(int N,int B,vector<int> S,vector<int> T,vector<int> D) {
	::n=N;
	for (int i=0;i<B;i++) {
		g[S[i]].push_back({T[i],D[i]});
		g[T[i]].push_back({S[i],D[i]});
	}
	init();
	update(0);
}

void ReceiveB(bool y) {
	num=num*2+y;
	cnt++;
	if (st==1&&cnt==9) {
//		printf("B recieved %d\n",num);
		cnt=0;
		if (num>d) {
			for (int i=10;i>=0;i--) SendB(x>>i&1);
			act[x]=1;
			update(x);
			num=0;
			st=1;
		} else {
			wei=num;
			cnt=0;
			num=0;
			st=2;
		}
	}
	if (st==2&&cnt==11) {
		cnt=0;
		dist[num]=mx+wei;
		act[num]=1;
		update(num);
		num=0;
		st=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