Submission #1105372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105372		nghia0912	Hotspot (NOI17_hotspot)	C++17	100 / 100	719 ms	1224 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];
long double E[N];
ll d[N], d2[N];
long double f[N], f2[N];
vector<ii> cb;

void BFS(int st, int en){
    queue<int> q;
    for (int i = 0; i < n;++i){
        d[i] = 3e18;
        d2[i] = 3e18;
        f[i] = 0;
        f2[i] = 0;
    }
    f[st] = 1;
    d[st] = 0;
    d2[en] = 0;
    f2[en] = 1;
    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];
            }
        }
    }
    q.push(en);
    while (!q.empty()){
        int u = q.front();q.pop();
        for (auto v : adj[u]){
            if (d2[u] + 1 < d2[v]){
                d2[v] = d2[u] + 1;
                f2[v] = f2[u];
                q.push(v);
            }
            else if (d2[u] + 1 == d2[v]){
                f2[v] += f2[u];
            }
        }
    }
    for (int i = 0; i < n; ++i){
        if (d[i] + d2[i] != d[en])continue;
        long double cc = f[i] * f2[i];
        E[i] += cc / f[en];
//        cout << "Cmm " << st << " " << i << " " << cc << " " << 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:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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