Submission #1105355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105355		monaxia	Hotspot (NOI17_hotspot)	C++17	0 / 100	6 ms	4688 KiB

hotspot

// credit: Mai Hong Kien

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define mod (long long)(1e9 + 7)
#define eps (long long)(1e-9)
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ll LIMIT = 2e3 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random (ll l, ll r){return uniform_int_distribution <ll> (l, r)(rng);}


void solve(){
    ll n, m;
    long double mx = 0, res = 0;
    cin >> n >> m;

    vector <vector <ll>> graph(n + 1), dist(n + 1, vector <ll> (n + 1, INT_MAX)), path(n + 1, vector <ll> (m + 1, 0));
    vector <long double> e(n + 1, 0);
    vector <pair <ll, ll>> range;

    for(ll i = 1; i <= m; i ++){
        ll u, v;
        cin >> u >> v;

        graph[u].pb(v);
        graph[v].pb(u);
    }

    for(ll i = 0; i < n; i ++){
        dist[i][i] = 0;
        path[i][i] = 1;

        vector <ll> v(n + 1, 0);
        queue <ll> q;

        q.push(i);

        while(!q.empty()){
            ll s = q.front();
            for(auto& x : graph[s]){
                if(dist[i][x] > dist[i][s] + 1) {
                    dist[i][x] = dist[i][s] + 1;
                    path[i][x] = path[i][s];
                } 

                else if(dist[i][x] == dist[i][s] + 1) path[i][x] += path[i][s];

                if(v[x]) continue;
                v[x] = 1;
                q.push(x);
            }

            q.pop();
        }
    }

    ll k;
    cin >> k;

    for(ll i = 1; i <= k; i ++){
        ll u, v;
        cin >> u >> v;

        range.pb({u, v});
    }

    for(ll i = 0; i < n; i ++){
        for(auto& x : range){
            if(dist[i][x.fr] + dist[i][x.sc] > dist[x.fr][x.sc]) continue;
            e[i] += ld(dist[i][x.fr] * dist[i][x.sc]) / ld(dist[x.fr][x.sc]);
        }

        if(e[i] > mx) mx = e[i], res = i;
    }

    cout << res + 1;
}


signed main()
{
    // cin.tie(0)->sync_with_stdio(0);
 
    if(fopen("TOY.inp", "r")){
        freopen("TOY.inp", "r", stdin);
        freopen("TOY.out", "w", stdout);
    }
    
    // cout << 1; return 0;

    ll n = 1;

    // cin >> n;

    while(n) {
        solve();
        n --;
        cout << "\n";
    }
 
    // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen("TOY.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("TOY.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