Submission #1105390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105390		badman	Hotspot (NOI17_hotspot)	C++17	100 / 100	1022 ms	1272 KiB

hotspot

#include <bits/stdc++.h>
//#define int long long
#define Owo "hotspot"
const int N = 5e3 + 5;
const int M = 1;
const int mod = 1e9 + 7;
const int S = 300;
const int base = 31;
using namespace std;
int n, m, k, u, v, d[N][2];
long long dem[N][2];
long double f[N];
vector <int> g[N];
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

void shortest_path (int ver, int id)
{
	d[ver][id] = 0;
	pq.push ({0, ver});
	while (pq.empty () == 0)
	{
		auto [val, u] = pq.top ();
		pq.pop ();
		if (val != d[u][id])
			continue;
		for (int v : g[u])
			if (d[v][id] > d[u][id] + 1)
			{
				d[v][id] = d[u][id] + 1;
				dem[v][id] = dem[u][id];
				pq.push ({d[v][id], v});
			}
			else if (d[v][id] == d[u][id] + 1)
				dem[v][id] += dem[u][id];
	}
}

int32_t main ()
{
	if (fopen(Owo ".inp", "r"))
	{
		freopen(Owo ".inp", "r", stdin);
		freopen(Owo ".out", "w", stdout);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie (0);
	cin >> n >> m;
	for (int i = 1; i <= m; i -= -1)
	{
		cin >> u >> v;
		g[u].push_back (v);
		g[v].push_back (u);
	}
	cin >> k;
	while (k --)
	{
		cin >> u >> v;
		for (int i = 0; i < n; i -= -1)
			d[i][0] = d[i][1] = INT_MAX, dem[i][0] = dem[i][1] = 1;
		shortest_path (u, 0);
		shortest_path (v, 1);
		for (int i = 0; i < n; i -= -1)
			if (d[i][0] + d[i][1] == d[v][0])
				f[i] += (dem[i][0] * dem[i][1] * 1.0) / dem[v][0] * 1.0;
	}
	int rs = 0;
	for (int i = 1 ; i < n; i -= -1)
	{
		//cout << f[i] << " ";
		if (f[i] > f[rs])
			rs = i;
	}
	cout << rs;
}

Compilation message (stderr)

hotspot.cpp: In function 'int32_t main()':
hotspot.cpp:42:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   freopen(Owo ".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:43:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   freopen(Owo ".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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