Submission #293170

#	Time	Username	Problem	Language	Result	Execution time	Memory
293170		Berted	Hotspot (NOI17_hotspot)	C++14	100 / 100	2043 ms	1992 KiB

hotspot

#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int,int>
#define ppi pair<int,pii>
#define fst first
#define snd second
#define vi vector<int>
#define pub push_back
using namespace std;
vector<vi> adj;int n,m,k,a,b,cr[5001][2]={},dst[5001]={};bool bt[5001]={};
double lk[5001]={};
queue<ppi> q;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=0;i<n;i++) {adj.pub(vi());}
	for (int i=0;i<m;i++) {cin>>a>>b;adj[a].pub(b);adj[b].pub(a);}
	cin>>k;
	for (int i=0;i<k;i++)
	{
		cin>>a>>b;
		for (int j=0;j<n;j++) {dst[j] = -1;bt[j]=0;}
		q.push({a,{0,-1}});
		while (!q.empty())
		{
			ppi dt = q.front();q.pop();
			
			if (dst[dt.fst]==-1)
			{
				dst[dt.fst] = dt.snd.fst;
				cr[dt.fst][0] = ((dt.snd.snd==-1)?(1):cr[dt.snd.snd][0]);
				for (auto v:adj[dt.fst]) {q.push({v,{dt.snd.fst+1,dt.fst}});}
			}
			else if (dst[dt.fst]==dt.snd.fst) {cr[dt.fst][0]+=((dt.snd.snd==-1)?1:cr[dt.snd.snd][0]);}
			//
		}
		q.push({b,{dst[b],-1}});
		while (!q.empty())
		{
			ppi dt = q.front();q.pop();
			cr[dt.fst][1]+=((dt.snd.snd==-1)?1:cr[dt.snd.snd][1]);
			if (!bt[dt.fst])
			{
				bt[dt.fst] = 1;
				for (auto v:adj[dt.fst]) 
				{
					if (dst[v] == dt.snd.fst-1 && dst[v] >= 0) {q.push({v,{dt.snd.fst-1,dt.fst}});}
				}
			}
		}
		//cout<<cr[b][0]<<"\n";
		for (int i=0;i<n;i++)
		{
			//cout<<i<<" "<<cr[i][0]<<" "<<cr[i][1]<<" "<<dst[i]<<"\n";
			lk[i] += (double) cr[i][0] * cr[i][1] / cr[b][0];
		}
		for (int i=0;i<n;i++) {cr[i][0] = cr[i][1] = 0;}
	}
	int mx = 0;
	for (int i=1;i<n;i++)
	{
		if (lk[i]>lk[mx]) {mx = i;}
		//cout<<i<<" "<<lk[i]<<"\n";
	}
	cout<<mx<<"\n";
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36