Submission #828714

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828714	2023-08-17T14:07:38 Z	NK_	Hotspot (NOI17_hotspot)	C++17	20 / 100	6 ms	7220 KB

hotspot

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;
using db = long double;


const db eps = 1e-9;
const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N, M; cin >> N >> M;
	V<vi> adj(N); for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	V<vi> ways(N, vi(N)), dst(N, vi(N, INF));

	auto bfs = [&](int r) {
		if (ways[r][r] != 0) return;
		vi vis(N, 0);
		queue<int> q; q.push(r);
		ways[r][r] = 1, dst[r][r] = 0;

		while(sz(q)) {
			int u = q.front(); q.pop();

			if (vis[u]) continue;
			vis[u] = 1;

			for(auto& v : adj[u]) {
				if (dst[r][v] > (dst[r][u] + 1)) {
					dst[r][v] = dst[r][u] + 1; ways[r][v] = 0;
					q.push(v); 
				}
				if (dst[r][v] == (dst[r][u] + 1)) {
					ways[r][v] += ways[r][u];
				}
			}
		}
	};

	int K; cin >> K;
	vpi Q(K);
	for(int i = 0; i < K; i++) {
		int a, b; cin >> a >> b;
		Q[i] = mp(a, b);
		bfs(a); 
	}

	for(int a = 0; a < N; a++) for(int b = 0; b < N; b++) if (dst[a][b] == INF) {
		dst[a][b] = dst[b][a];
		ways[a][b] = ways[b][a];
	}


	db best = -1; int ans = -1;

	auto through = [&](int a, int w, int b) {
		if ((dst[a][w] + dst[w][b]) != dst[a][b]) return db(0);

		int all = ways[a][b];
		int allw = ways[a][w] * ways[w][b];

		return db(allw) / db(all);
	};

	for(int u = 0; u < N; u++) {
		db E = 0;
		for(int i = 0; i < K; i++) E += through(Q[i].f, u, Q[i].s);

		if (best + eps < E) ans = u, best = E;
	}

	cout << ans << nl;

	exit(0-0);
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2388 KB	Output is correct
2	Correct	4 ms	5460 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1108 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	2516 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2388 KB	Output is correct
2	Correct	4 ms	5460 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1108 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	2516 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	2 ms	2648 KB	Output is correct
10	Correct	4 ms	5588 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	1108 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2388 KB	Output is correct
2	Correct	4 ms	5460 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1108 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	2516 KB	Output is correct
8	Correct	1 ms	1108 KB	Output is correct
9	Correct	2 ms	3284 KB	Output is correct
10	Correct	2 ms	2764 KB	Output is correct
11	Correct	4 ms	5844 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	1236 KB	Output is correct

Subtask #4
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2388 KB	Output is correct
2	Correct	4 ms	5460 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1108 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	2516 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	2 ms	2648 KB	Output is correct
10	Correct	4 ms	5588 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	1108 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	1 ms	1108 KB	Output is correct
16	Correct	2 ms	3284 KB	Output is correct
17	Correct	2 ms	2764 KB	Output is correct
18	Correct	4 ms	5844 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	1236 KB	Output is correct
22	Incorrect	1 ms	1620 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2388 KB	Output is correct
2	Correct	4 ms	5460 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1108 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	2516 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	2 ms	2648 KB	Output is correct
10	Correct	4 ms	5588 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	1108 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	1748 KB	Output is correct
17	Correct	5 ms	4436 KB	Output is correct
18	Correct	3 ms	3668 KB	Output is correct
19	Correct	6 ms	7220 KB	Output is correct
20	Incorrect	1 ms	800 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #6
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2388 KB	Output is correct
2	Correct	4 ms	5460 KB	Output is correct
3	Correct	3 ms	4692 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	1108 KB	Output is correct
6	Correct	1 ms	724 KB	Output is correct
7	Correct	2 ms	2516 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	2 ms	2648 KB	Output is correct
10	Correct	4 ms	5588 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	1108 KB	Output is correct
14	Correct	2 ms	3284 KB	Output is correct
15	Correct	1 ms	1108 KB	Output is correct
16	Correct	2 ms	3284 KB	Output is correct
17	Correct	2 ms	2764 KB	Output is correct
18	Correct	4 ms	5844 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	1236 KB	Output is correct
22	Incorrect	1 ms	1620 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Submission #828714

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 5.0 / 5.0

Subtask #3 11.0 / 11.0

Subtask #4 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
0 / 18.0

Subtask #5
0 / 26.0

Subtask #6
0 / 36.0