Submission #82371

#	Time	Username	Problem	Language	Result	Execution time	Memory
82371		user202729	007 (CEOI14_007)	C++17	100 / 100	641 ms	17500 KiB

007

// https://oj.uz/problem/view/CEOI14_007
#include<iostream>
auto&I=std::cin;auto&O=std::cout;

#include<vector>
#include<queue>

std::vector<std::vector<int>> adjl;
int INF=2e9;
std::vector<int> minDistTo(int node){
	std::vector<int> minDist(adjl.size(),INF);
	std::queue<int> q;
	q.push(node);minDist[node]=0;
	while(!q.empty()){
		node=q.front();q.pop();
		for(int adj:adjl[node])
			if(minDist[adj]==INF){
				minDist[adj]=minDist[node]+1;
				q.push(adj);
			}
	}
	return minDist;
}

int main(){
	int nnode,nedge,_007Start,nullStart,socket1,socket2;
	I>>nnode>>nedge>>_007Start>>nullStart>>socket1>>socket2;
	--_007Start;--nullStart;--socket1;--socket2;
	adjl.resize(nnode);
	for(int i=nedge;i-->0;){
		int u,v;I>>u>>v;--u;--v;
		adjl[u].push_back(v);
		adjl[v].push_back(u);
	}

	auto minDist007=minDistTo(_007Start);
	auto minDistNull=minDistTo(nullStart);
	auto minDistS1=minDistTo(socket1);
	auto minDistS2=minDistTo(socket2);

	/// Return whether 007 can prevent Dr. De Referenced Nullpointer from pulling the plug of a server
	auto check=[&](int breakfastTime){
		if(minDistNull[socket1]<breakfastTime+minDist007[socket1]||
				minDistNull[socket2]<breakfastTime+minDist007[socket2])return false;
		else if(minDistNull[socket1]>breakfastTime+minDist007[socket1]||
				minDistNull[socket2]>breakfastTime+minDist007[socket2])return true;

		// otherwise, the distance of both person to each socket is equal
		auto bestBranchPointValue=[&](std::vector<int> const& minDistNode){
			// find max k such that there is a node with dist k from (node) and is on the min path from
			// (node) to both sockets
			int maxK=-1;
			for(int n_=0;n_<nnode;++n_)
				if(minDistNode[n_]+minDistS1[n_]==minDistNode[socket1]&&
						minDistNode[n_]+minDistS2[n_]==minDistNode[socket2])
					maxK=std::max(maxK,minDistNode[n_]);
			return maxK;
		};

		if(bestBranchPointValue(minDistNull)>breakfastTime+bestBranchPointValue(minDist007))
			return false;
		else return true;
	};

	int ans=-1;
	for(int i=1<<20;i;i>>=1){
		ans+=i;
		if(!check(ans))
			ans-=i;
	}
	O<<ans<<'\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70