oj.uz

Submission #1105387

# Submission time Handle Problem Language Result Execution time Memory
1105387 2024-10-26T09:01:38 Z badman Hotspot (NOI17_hotspot) C++17
38 / 100
 9 ms 764 KB 
#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;
				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] += (long double)(dem[i][0] * dem[i][1]) / (long double) dem[v][0];
	}
	int rs = 0;
	for (int i = 0 ; i < n; i -= -1)
	{
		//cout << f[i] << " ";
		if (f[i] > f[rs])
			rs = i;
	}
	cout << rs;
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 3 ms 764 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 3 ms 592 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 3 ms 764 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 628 KB Output is correct
24 Correct 5 ms 592 KB Output is correct
25 Correct 9 ms 664 KB Output is correct
26 Correct 9 ms 592 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 7 ms 592 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Correct 5 ms 592 KB Output is correct
18 Incorrect 3 ms 760 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 592 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 3 ms 764 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 3 ms 760 KB Output is correct
23 Correct 3 ms 628 KB Output is correct
24 Correct 5 ms 592 KB Output is correct
25 Correct 9 ms 664 KB Output is correct
26 Correct 9 ms 592 KB Output is correct
27 Correct 2 ms 592 KB Output is correct
28 Correct 7 ms 592 KB Output is correct
29 Correct 2 ms 760 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 5 ms 592 KB Output is correct
32 Incorrect 3 ms 760 KB Output isn't correct
33 Halted 0 ms 0 KB -