제출 #592153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592153		angelo_torres	Hotspot (NOI17_hotspot)	C++17	35 / 100	799 ms	11132 KiB

hotspot

#include <bits/stdc++.h>
#define f(i,j,n) for(int i = j; i < n; ++i)
#define ff first
#define ss second
#define sz(v) (ll) v.size()


using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long double ld;

const int N = 5e3 + 20;
const ll inf = 2e9;
const ll mod = 1e9 + 7;

bool vis[N];
int n,m,k,A[N],B[N];
ll dis[N][N];
vi adj[N];
ll p[N][2];
ld sum[N];
int Ai,Bi;

void bfs(int v){
	f(i,0,n) vis[i] = 0;
	queue<int> q;
	q.push(v);
	p[v][0] = 1;
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		if(vis[cur]) continue;
		vis[cur] = 1;
		for(auto vs : adj[cur]){
			if(dis[Ai][vs] + dis[vs][Bi] != dis[Ai][Bi] or dis[Ai][vs] != dis[Ai][cur]+1) 
				continue;
			p[vs][0] += p[cur][0];
			q.push(vs);
		}
	}
}

void solve(){
	cin >> n >> m;
	f(i,0,n) f(j,0,n) dis[i][j] = 2000000000;
	f(i,0,m){
		int u,v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		dis[u][v] = dis[v][u] = 1;
	}
	cin >> k;
	f(i,0,k) cin >> A[i] >> B[i];
	f(i,0,n) dis[i][i] = 0;
	f(op,0,n){
		f(i,0,n){
			f(j,0,n){
				if(dis[i][j] > dis[i][op] + dis[op][j])
					dis[i][j] = dis[i][op] + dis[op][j];
			}
		}
	}
	f(id,0,k){
		Ai = A[id], Bi = B[id];
		bfs(Ai);
		f(i,0,n) p[i][1] = p[i][0], p[i][0] = 0;
		swap(Ai,Bi);
		bfs(Ai);
		swap(Ai,Bi);
		// f(i,0,n) cout << p[i][0] << " " << p[i][1] << endl;
		f(i,0,n){
			ld pAi = (ld) p[i][1], pBi = (ld) p[i][0];
			sum[i] += (pAi*pBi)/((ld) p[Bi][1]);
		}
	}
	int cy = 0;
	ld ans = sum[0];
	f(i,0,n){
		if(sum[i] > ans) ans = sum[i], cy = i;
	}
	cout << cy << endl;

}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
	// cin >> tc;
	while(tc--) solve();	
	return 0;
}

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