Submission #674919

#	Time	Username	Problem	Language	Result	Execution time	Memory
674919		QwertyPi	Hotspot (NOI17_hotspot)	C++14	100 / 100	737 ms	1284 KiB

hotspot

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5011;
long double Exp[MAXN];
bool vis[MAXN];
vector<int> G[MAXN];
vector<int> du(MAXN), dv(MAXN), cu(MAXN), cv(MAXN); 
void bfs(int u, int v, vector<int>& c, vector<int>& d){
	fill(c.begin(), c.end(), 0);
	fill(d.begin(), d.end(), 1 << 30);
	fill(vis, vis + MAXN, 0);
	deque<int> dq; dq.push_back(u); d[u] = 0; c[u] = 1; vis[u] = true;
	while(dq.size()){
		int t = dq.front(); dq.pop_front();
		for(auto i : G[t]){
			if(d[t] + 1 < d[i]){
				c[i] = c[t];
				d[i] = d[t] + 1;
				if(!vis[i]) dq.push_back(i), vis[i] = true;
			}else if(d[t] + 1 == d[i]){
				c[i] += c[t];
			}
		}
	}
}

bool ok[MAXN];
int n, m;
void solve(int u, int v){
	bfs(u, v, cu, du); bfs(v, u, cv, dv);
	
	int q = cu[v];
	for(int i = 0; i < n; i++){
		int p = cu[i] * cv[i] * (du[i] + dv[i] == du[v]);
		Exp[i] += (long double) p / q;
	}
}

int main(){
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int a, b; cin >> a >> b;
		solve(a, b);
	}
	
	int ans = 0;
	for(int i = 1; i < n; i++){
		if(Exp[ans] < Exp[i]) ans = i;
	}
	cout << ans << endl;
}

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