답안 #828714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828714 2023-08-17T14:07:38 Z NK_ Hotspot (NOI17_hotspot) C++17
20 / 100
6 ms 7220 KB
// 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);
}					
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -