Submission #854329

#	Time	Username	Problem	Language	Result	Execution time	Memory
854329		annabeth9680	Hotspot (NOI17_hotspot)	C++17	100 / 100	586 ms	1612 KiB

hotspot

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5011;
vector<int> adj[MAXN];
long double ans[MAXN];
bool vis[MAXN];
int N;
vector<int> df(MAXN), ds(MAXN), nf(MAXN), ns(MAXN);
void bfs(int src, int dest, vector<int> &nums, vector<int> &dist){
    fill(nums.begin(),nums.end(),0); fill(dist.begin(),dist.end(),1<<30);
    memset(vis,false,sizeof(vis));
    vis[src] = true; dist[src] = 0; nums[src] = 1;
    deque<int> q; q.push_back(src);
    while(!q.empty()){
        int u = q.front(); q.pop_front();
        for(int v : adj[u]){
            if(dist[u]+1 < dist[v]){
                nums[v] = nums[u];
                dist[v] = dist[u]+1;
                if(!vis[v]){
                    q.push_back(v);
                    vis[v] = true;
                }
            }
            else if(dist[u]+1 == dist[v]){
                nums[v] += nums[u];
            }
        }
    }
}
void solve(int src, int dest){
    bfs(src,dest,nf,df); bfs(dest,src,ns,ds);
    int num = nf[dest];
    for(int i = 0;i<N;++i){
        if(df[i]+ds[i] == df[dest]){
            int cur = nf[i]*ns[i];
            ans[i] += (long double) cur/num;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int M; cin >> N >> M;
    for(int i = 0;i<M;++i){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[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 ret = 0;
    for(int i = 0;i<N;++i){
        if(ans[i] > ans[ret]) ret = i;
    }
    cout << ret << "\n";
    return 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