Submission #676472

#	Time	Username	Problem	Language	Result	Execution time	Memory
676472		penguin133	Hotspot (NOI17_hotspot)	C++17	100 / 100	374 ms	1648 KiB

hotspot

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m,q;
vector<int>v[5005];
long double ans[5005], cnt[5005];
int vis[5005];
pi dist[5005];
void solve(){
	cin >> n >> m;
	while(m--){
		int x,y; cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	queue<int>qu;
	cin >> q;
	while(q--){
		int x, y; cin >> x >> y;
		qu.push(x);
		for(int i=0;i<=n;i++)dist[i] = {1e18, 0}, vis[i] = 0;
		dist[x] = {0, 1};
		for(int i=0;i<=n;i++)cnt[i] = 0;
		while(!qu.empty()){
			int bru = qu.front(); qu.pop();
			//cout << bru << '\n';
			for(auto i : v[bru]){
				if(dist[i].fi > dist[bru].fi + 1)dist[i] = dist[bru], dist[i].fi++, qu.push(i);
				else if(dist[i].fi == dist[bru].fi + 1)dist[i].se += dist[bru].se;
			}
		}
		//cerr << dist[y].se << '\n';
		int cur = dist[y].se;
		assert(cur != 0);
		cnt[y] = 1.0L;
		qu.push(y);
		while(!qu.empty()){
			int bt = qu.front(); qu.pop();
			if(vis[bt])continue;
			vis[bt] = 1;
			ans[bt] += cnt[bt];
			for(auto i : v[bt]){
				if(dist[i].fi == dist[bt].fi - 1){
					qu.push(i);
					cnt[i] += (long double)((long double)dist[i].se/(long double)dist[bt].se * cnt[bt]);
				}
			}
		}
	}
	long double fin = 0.0;
	int in = 0;
	for(int i=0;i<=n;i++)if(fin < ans[i])fin = ans[i], in = i;
	//for(int i=0;i<n;i++)cout << ans[i] << " ";
	//cout << '\n';
	cout << in << '\n';
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

hotspot.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main(){
      | ^~~~

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