Submission #828712

#	Time	Username	Problem	Language	Result	Execution time	Memory
828712		NK_	Hotspot (NOI17_hotspot)	C++17	100 / 100	610 ms	123540 KiB

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-10;
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;
		// cout << "BFS: " << r << endl;
		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();
			// cout << u << endl;

			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); 
					// cout << "NEI: " << v << endl;
				}
				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); bfs(b);
	}

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

		// cout << a << " " << w << " " << b << endl;
		// cout << all << " - " << allw << endl;

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

		// cout << u << " " << E << endl;

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

	cout << ans << nl;

	exit(0-0);
}					

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