oj.uz

Submission #1102925

# Submission time Handle Problem Language Result Execution time Memory
1102925 2024-10-19T08:59:07 Z Avocabo Hotspot (NOI17_hotspot) C++17
0 / 100
 3 ms 6480 KB 
#include <bits/stdc++.h>
using namespace std;

#define task "TRAINCENTER"
#define fi first
#define se second
#define pii pair <int, int>
#define pb push_back
#define ll long long 
#define pip pair <int, pii>
#define pli pair <ll, int>

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;

int myabs(int x)
{
    return x < 0 ? -x : x;
}

int n, m, k;
vector <int> g[N];
long long cnt[2][N], d[2][N];
double ans[N];

void inp()
{
    cin >> n >> m;
    for (int i=1; i<=m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> k;
}

void bfs(int id, int s)
{
    queue <int> q;
    for (int i=0; i<=n; ++i)
        d[id][i] = -1,
        cnt[id][i] = 0;
    d[id][s] = 0;
    q.push(s);
    cnt[id][s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : g[u])
        {
            if (d[id][v] == -1)
            {
                d[id][v] = d[id][u] + 1;
                cnt[id][v] = cnt[id][u];
                q.push(v);
            }
            else if (d[id][v] == d[id][u] + 1)
                cnt[id][v] += cnt[id][u];
        }
    }
}

void solve()
{
    while (k--)
    {
        int a, b;
        cin >> a >> b;
        bfs(0, a);
        bfs(1, b);
        double tmp = cnt[0][b];
        for (int i=0; i<n; ++i)
            if (d[0][i] + d[1][i] == d[0][b])
            {
                double tmp1 = (double)(cnt[0][i] * cnt[1][i]);
                ans[i] += (tmp1/tmp);
            }
    }
    int res = 0;
    for (int i=0; i<n; ++i)
        if (ans[i] > ans[res])
            res = i-1;
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    inp();
    solve();
    return 0;
}

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 3 ms 6480 KB Output is correct
4 Incorrect 2 ms 6480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 3 ms 6480 KB Output is correct
4 Incorrect 2 ms 6480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 3 ms 6480 KB Output is correct
4 Incorrect 2 ms 6480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 3 ms 6480 KB Output is correct
4 Incorrect 2 ms 6480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 3 ms 6480 KB Output is correct
4 Incorrect 2 ms 6480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Correct 3 ms 6480 KB Output is correct
4 Incorrect 2 ms 6480 KB Output isn't correct
5 Halted 0 ms 0 KB -