oj.uz

Submission #1105352

# Submission time Handle Problem Language Result Execution time Memory
1105352 2024-10-26T08:29:27 Z monaxia Hotspot (NOI17_hotspot) C++17
9 / 100
 17 ms 5712 KB 
// 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(){
    int n, m;
    long double mx = 0, res = 0;
    cin >> n >> m;

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

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

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

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

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

        q.push(i);

        while(!q.empty()){
            int 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();
        }
    }

    int k;
    cin >> k;

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

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

    for(int 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;
}


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

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2640 KB Output is correct
2 Correct 13 ms 5644 KB Output is correct
3 Correct 11 ms 4856 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 6 ms 2896 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2640 KB Output is correct
2 Correct 13 ms 5644 KB Output is correct
3 Correct 11 ms 4856 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 6 ms 2896 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 6 ms 2640 KB Output is correct
10 Correct 17 ms 5712 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 3 ms 1320 KB Output is correct
14 Correct 8 ms 3440 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2640 KB Output is correct
2 Correct 13 ms 5644 KB Output is correct
3 Correct 11 ms 4856 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 6 ms 2896 KB Output is correct
8 Incorrect 4 ms 1360 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2640 KB Output is correct
2 Correct 13 ms 5644 KB Output is correct
3 Correct 11 ms 4856 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 6 ms 2896 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 6 ms 2640 KB Output is correct
10 Correct 17 ms 5712 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 3 ms 1320 KB Output is correct
14 Correct 8 ms 3440 KB Output is correct
15 Incorrect 4 ms 1360 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2640 KB Output is correct
2 Correct 13 ms 5644 KB Output is correct
3 Correct 11 ms 4856 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 6 ms 2896 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 6 ms 2640 KB Output is correct
10 Correct 17 ms 5712 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 3 ms 1320 KB Output is correct
14 Correct 8 ms 3440 KB Output is correct
15 Incorrect 13 ms 4556 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2640 KB Output is correct
2 Correct 13 ms 5644 KB Output is correct
3 Correct 11 ms 4856 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 6 ms 2896 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 6 ms 2640 KB Output is correct
10 Correct 17 ms 5712 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 3 ms 1320 KB Output is correct
14 Correct 8 ms 3440 KB Output is correct
15 Incorrect 4 ms 1360 KB Output isn't correct
16 Halted 0 ms 0 KB -