Submission #1179633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179633		PlayVoltz	Two Transportations (JOI19_transportations)	C++20	100 / 100	495 ms	42736 KiB

Azer

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

namespace{
	int counter=0, val=0, phase=0, tempval;
	vector<int> dist, done, notdone;
	vector<bool> del;
	vector<deque<pii> > graph;
}

void InitA(int n, int a, vector<int> u, vector<int> v, vector<int> c){
	done.clear();
	dist.clear();
	graph.clear();
	del.clear();
	del.resize(n, 0);
	done.resize(1, 0);
	dist.resize(n, INT_MIN/2);
	graph.resize(n);
	dist[0]=counter=val=phase=0;
	del[0]=1;
	for (int i=1; i<n; ++i)notdone.pb(i);
	for (int i=0; i<a; ++i){
		graph[u[i]].pb(mp(c[i], v[i]));
		graph[v[i]].pb(mp(c[i], u[i]));
	}
	for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
}

void ReceiveA(bool x){
	++counter;
	val=val*2+x;
	if (!phase&&counter==9){
		int dj=INT_MAX/2, best;
		for (auto node:done){
			while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
			if (graph[node].empty())continue;
			if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
		}
		if (dj-*max_element(dist.begin(), dist.end())<val){
			SendA(0);
			done.pb(best);
			del[best]=1;
			int id=0;
			for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
			notdone.erase(find(notdone.begin(), notdone.end(), best));
			for (int i=(int)log2(notdone.size()+1); i>=0; --i)SendA((1<<i)&id);
			for (int i=8; i>=0; --i)SendA((1<<i)&(dj-*max_element(dist.begin(), dist.end())));
			dist[best]=dj;
		}
		else{
			SendA(1);
			phase=1;
		}
		counter=val=0;
	}
	if (phase==1&&counter==(int)log2(notdone.size())+1){
		tempval=val;
		phase=2;
		counter=val=0;
	}
	if (phase==2&&counter==9){
		int best=notdone[tempval];
		dist[best]=val+*max_element(dist.begin(), dist.end());
		done.pb(best);
		del[best]=1;
		notdone.erase(find(notdone.begin(), notdone.end(), best));
		phase=counter=val=0;
	}
}

vector<int> Answer(){
	return dist;
}

Baijan

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

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

namespace{
	int counter=0, val=0, phase=0, tempval, dj=INT_MAX/2, best;
	vector<int> dist, done, notdone;
	vector<bool> del;
	vector<deque<pii> > graph;
	
	void sendover(){
		if (notdone.empty())return;
		dj=INT_MAX/2;
		for (auto node:done){
			while (graph[node].size()&&del[graph[node][0].se])graph[node].pop_front();
			if (graph[node].empty())continue;
			if (dist[node]+graph[node][0].fi<dj)dj=dist[node]+graph[node][0].fi, best=graph[node][0].se;
		}
		if (dj-*max_element(dist.begin(), dist.end())>500)for (int i=8; i>=0; --i)SendB(1);
		else for (int i=8; i>=0; --i)SendB((1<<i)&(dj-*max_element(dist.begin(), dist.end())));
	}
}

void InitB(int n, int a, vector<int> u, vector<int> v, vector<int> c){
	done.clear();
	dist.clear();
	graph.clear();
	del.clear();
	del.resize(n, 0);
	done.resize(1, 0);
	dist.resize(n, INT_MIN/2);
	graph.resize(n);
	dist[0]=counter=val=phase=0;
	del[0]=1;
	for (int i=1; i<n; ++i)notdone.pb(i);
	for (int i=0; i<a; ++i){
		graph[u[i]].pb(mp(c[i], v[i]));
		graph[v[i]].pb(mp(c[i], u[i]));
	}
	for (int i=0; i<n; ++i)sort(graph[i].begin(), graph[i].end());
	sendover();
}

void ReceiveB(bool x){
	++counter;
	val=val*2+x;
	if (!phase){
		if (val){
			done.pb(best);
			del[best]=1;
			int id=0;
			for (int i=0; i<notdone.size(); ++i)if (notdone[i]==best)id=i;
			notdone.erase(find(notdone.begin(), notdone.end(), best));
			for (int i=log2(notdone.size()+1); i>=0; --i)SendB((1<<i)&id);
			for (int i=8; i>=0; --i)SendB((1<<i)&(dj-*max_element(dist.begin(), dist.end())));
			dist[best]=dj;
			sendover();
		}
		else phase=1;
		val=counter=0;
	}
	if (phase==1&&counter==(int)log2(notdone.size())+1){
		tempval=val;
		phase=2;
		counter=val=0;
	}
	if (phase==2&&counter==9){
		int best=notdone[tempval];
		dist[best]=val+*max_element(dist.begin(), dist.end());
		done.pb(best);
		del[best]=1;
		notdone.erase(find(notdone.begin(), notdone.end(), best));
		phase=counter=val=0;
		sendover();
	}
}

• 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