Submission #1105349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105349		nghia0912	Hotspot (NOI17_hotspot)	C++17	0 / 100	1 ms	592 KiB

hotspot

#define COPYRIGHT CODE BY TRINH TUAN NGHIA
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("popcnt")
#define Boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define endl "\n"
#define st first
#define nd second
#define ii pair <int,int>
#define iii pair <int,ii>
#define iiii pair <ii,ii>
#define pb push_back
#define NAME "traincentre"
using namespace std;
const int N = 5e3 + 10;
const int M = 4e4 + 10;
int n, m, k;
vector<int> adj[N];
double E[N];
ll d[N];
ll f[N];
vector<ii> cb;

void BFS(int st, int en){
    queue<int> q;
    for (int i = 0; i < n;++i){
        d[i] = 1e18;
        f[i] = 0;
    }
    f[st] = 1;
    d[st] = 0;
    q.push(st);
    while (!q.empty()){
        int u = q.front();q.pop();
        for (auto v : adj[u]){
            if (d[u] + 1 < d[v]){
                d[v] = d[u] + 1;
                f[v] = f[u];
                q.push(v);
            }
            else if (d[u] + 1 == d[v]){
                f[v] += f[u];
            }
        }
    }
    f[st] = f[en];
    for (int i = 0; i  < n; ++i){
        E[i] += double(1) * f[i] / f[en];
//        cout << "Cmm " << f[i] << " " << f[en] << endl;
    }
}
void inp (){
    cin >>n  >> m;
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin >> k;
    for (int i =1; i <= k; ++i){
        int x, y;
        cin>> x >>  y;
        cb.pb({x,  y});
    }
}
void solve(){
    for (auto x : cb){
        BFS(x.st, x.nd);
    }
    int mx = -1;
    for (int i= 0; i < n; ++i){
        if (mx == -1 or E[i] > E[mx]){
            mx = i;
        }
//        cout << i << " " << E[i] << endl;
    }
    cout <<mx << endl;
}
signed main (){
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    Boost;
    inp();
    solve();
}
/*
input

*/

/*
output

*/

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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