oj.uz

Submission #1105363

# Submission time Handle Problem Language Result Execution time Memory
1105363 2024-10-26T08:38:11 Z whoknow Hotspot (NOI17_hotspot) C++17
38 / 100
 5 ms 848 KB 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define F first
#define S second
#define MAXN 5005
#define MAXEDGE 40005
#define ii pair<ll,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, m, k;
vector<int>g[MAXN];
namespace sub1
{
double dp[MAXN];
ii d[MAXN][2];
bool visited[MAXN];
void bfs(int st, int j)
{
    for(int i = 0; i <= n; i++)
    {
        visited[i]=0;
        d[i][j] = {1e18, 0};
    }
    queue<int>q;
    q.push(st);
    d[st][j] = {0, 1};
    while(q.empty() != 1)
    {
        int u = q.front();
        q.pop();
        visited[u]=1;
        for(int v : g[u])
        {
            if(visited[v])
                continue;
            if(d[v][j].F > d[u][j].F + 1)
            {
                d[v][j] = {d[u][j].F + 1, d[u][j].S};
                q.push(v);
            }
            else if(d[v][j].F == d[u][j].F + 1)
                d[v][j].S += d[u][j].S;
        }
    }
}
void calc(int st, int ed)
{
    for(int i=0;i<n;i++)
    {
        if(d[i][0].F+d[i][1].F==d[ed][0].F)
        {
            double t=1.0*d[i][0].S*d[i][1].S,t1=d[ed][0].S;
            dp[i]+=1.0*t/1.0*t1;
        }
    }
}
void solve()
{
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int x, y;
        cin >> x >> y;
        bfs(x, 0);
        bfs(y, 1);
        calc(x, y);
    }
    int res = 0;
    for(int i = 0; i < n; i++)
        if(dp[i] > dp[res])
            res = i;
    cout << res;
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    sub1::solve();
}
/**
5 5
0 1
1 2
2 3
3 4
4 0
2
0 2
0 4

**/

Compilation message

hotspot.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main()
      | ^~~~

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 592 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 592 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 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct

Subtask #3
11.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 592 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 760 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 3 ms 764 KB Output is correct

Subtask #4
18.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 592 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 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 760 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 3 ms 764 KB Output is correct
22 Correct 1 ms 592 KB Output is correct
23 Correct 1 ms 592 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 3 ms 592 KB Output is correct
27 Correct 1 ms 508 KB Output is correct
28 Correct 2 ms 592 KB Output is correct

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 592 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 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 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 592 KB Output is correct
16 Correct 1 ms 760 KB Output is correct
17 Incorrect 5 ms 848 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 592 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 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 1 ms 760 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Correct 2 ms 592 KB Output is correct
18 Correct 2 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 3 ms 764 KB Output is correct
22 Correct 1 ms 592 KB Output is correct
23 Correct 1 ms 592 KB Output is correct
24 Correct 2 ms 592 KB Output is correct
25 Correct 2 ms 592 KB Output is correct
26 Correct 3 ms 592 KB Output is correct
27 Correct 1 ms 508 KB Output is correct
28 Correct 2 ms 592 KB Output is correct
29 Correct 2 ms 592 KB Output is correct
30 Correct 1 ms 760 KB Output is correct
31 Incorrect 5 ms 848 KB Output isn't correct
32 Halted 0 ms 0 KB -