Submission #1105371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105371		monaxia	Hotspot (NOI17_hotspot)	C++17	9 / 100	82 ms	41032 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;
                else e[i] += ld(path[i][x.fr] * path[i][x.sc]) / ld(path[x.fr][x.sc]);
                // cout << x.fr << " " << x.sc << " " << ld(dist[i][x.fr] * dist[i][x.sc]) / ld(dist[x.fr][x.sc]) << "\n";
            }
     
            if(e[i] > mx) mx = e[i], res = i;
            // cout << e[i] << " ";
            // cout << "\n";
        }
     
        cout << res;
    }
     
     
    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:98:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |             freopen("TOY.inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
hotspot.cpp:99:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |             freopen("TOY.out", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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