oj.uz

Submission #1105358

# Submission time Handle Problem Language Result Execution time Memory
1105358 2024-10-26T08:37:08 Z nghia0912 Hotspot (NOI17_hotspot) C++17
9 / 100
 3 ms 760 KB 
#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];
ll 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] = 1e18;
        d2[i] = 1e18;
        f[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 << 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

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 760 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Incorrect 1 ms 592 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 760 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Incorrect 1 ms 592 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 760 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 760 KB Output is correct
16 Correct 1 ms 592 KB Output is correct
17 Incorrect 3 ms 592 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 760 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 756 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 760 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Incorrect 1 ms 592 KB Output isn't correct
16 Halted 0 ms 0 KB -