답안 #1105387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1105387	2024-10-26T09:01:38 Z	badman	Hotspot (NOI17_hotspot)	C++17	38 / 100	9 ms	764 KB

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;
				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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #1105387

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 5.0 / 5.0

Subtask #3 11.0 / 11.0

Subtask #4 18.0 / 18.0

Subtask #5 0 / 26.0

Subtask #6 0 / 36.0

Subtask #1
4.0 / 4.0

Subtask #2
5.0 / 5.0

Subtask #3
11.0 / 11.0

Subtask #4
18.0 / 18.0

Subtask #5
0 / 26.0

Subtask #6
0 / 36.0