oj.uz

Submission #619913

# Submission time Handle Problem Language Result Execution time Memory
619913 2022-08-02T17:13:06 Z PoonYaPat Hotspot (NOI17_hotspot) C++14
100 / 100
 1553 ms 338468 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m,k,d[5001][5001],ans_node,x[2001],y[2001];
vector<int> adj[5001];
queue<int> q;
long double ans,cnt[5001][5001];

void bfs(int x) {
    memset(d[x],0x3f,sizeof(d[x]));

    q.push(x);
    d[x][x]=0;
    cnt[x][x]=1;

    while (!q.empty()) {
        int a=q.front();
        q.pop();

        for (auto s : adj[a]) {
            if (d[x][s]>d[x][a]+1) {
                d[x][s]=d[x][a]+1;
                cnt[x][s]+=cnt[x][a];
                q.push(s);
            } else if (d[x][s]==d[x][a]+1) cnt[x][s]+=cnt[x][a];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin>>k;
    for (int i=0; i<k; ++i) cin>>x[i]>>y[i];
    for (int i=0; i<n; ++i) bfs(i);
    for (int i=0; i<n; ++i) {
        long double sum=0;
        for (int j=0; j<k; ++j) {
            if (d[x[j]][i]+d[i][y[j]]==d[x[j]][y[j]]) {
                sum+=(cnt[x[j]][i]*cnt[i][y[j]])/cnt[x[j]][y[j]];
            }
        }
        if (sum>ans) ans_node=i,ans=sum;
    }
    cout<<ans_node;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16980 KB Output is correct
2 Correct 26 ms 29660 KB Output is correct
3 Correct 31 ms 26484 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 5 ms 7124 KB Output is correct
7 Correct 13 ms 17364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16980 KB Output is correct
2 Correct 26 ms 29660 KB Output is correct
3 Correct 31 ms 26484 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 5 ms 7124 KB Output is correct
7 Correct 13 ms 17364 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 16 ms 17604 KB Output is correct
10 Correct 35 ms 30460 KB Output is correct
11 Correct 1 ms 3028 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 16 ms 20692 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16980 KB Output is correct
2 Correct 26 ms 29660 KB Output is correct
3 Correct 31 ms 26484 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 5 ms 7124 KB Output is correct
7 Correct 13 ms 17364 KB Output is correct
8 Correct 7 ms 10108 KB Output is correct
9 Correct 17 ms 21008 KB Output is correct
10 Correct 13 ms 18260 KB Output is correct
11 Correct 27 ms 31180 KB Output is correct
12 Correct 2 ms 3520 KB Output is correct
13 Correct 1 ms 1748 KB Output is correct
14 Correct 7 ms 10324 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16980 KB Output is correct
2 Correct 26 ms 29660 KB Output is correct
3 Correct 31 ms 26484 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 5 ms 7124 KB Output is correct
7 Correct 13 ms 17364 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 16 ms 17604 KB Output is correct
10 Correct 35 ms 30460 KB Output is correct
11 Correct 1 ms 3028 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 16 ms 20692 KB Output is correct
15 Correct 7 ms 10108 KB Output is correct
16 Correct 17 ms 21008 KB Output is correct
17 Correct 13 ms 18260 KB Output is correct
18 Correct 27 ms 31180 KB Output is correct
19 Correct 2 ms 3520 KB Output is correct
20 Correct 1 ms 1748 KB Output is correct
21 Correct 7 ms 10324 KB Output is correct
22 Correct 12 ms 13012 KB Output is correct
23 Correct 10 ms 10584 KB Output is correct
24 Correct 20 ms 21696 KB Output is correct
25 Correct 33 ms 35396 KB Output is correct
26 Correct 30 ms 31948 KB Output is correct
27 Correct 3 ms 3924 KB Output is correct
28 Correct 10 ms 13304 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16980 KB Output is correct
2 Correct 26 ms 29660 KB Output is correct
3 Correct 31 ms 26484 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 5 ms 7124 KB Output is correct
7 Correct 13 ms 17364 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 16 ms 17604 KB Output is correct
10 Correct 35 ms 30460 KB Output is correct
11 Correct 1 ms 3028 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 16 ms 20692 KB Output is correct
15 Correct 15 ms 4308 KB Output is correct
16 Correct 21 ms 13532 KB Output is correct
17 Correct 69 ms 25536 KB Output is correct
18 Correct 42 ms 22360 KB Output is correct
19 Correct 87 ms 36308 KB Output is correct
20 Correct 13 ms 6484 KB Output is correct
21 Correct 5 ms 4436 KB Output is correct

Subtask #6
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16980 KB Output is correct
2 Correct 26 ms 29660 KB Output is correct
3 Correct 31 ms 26484 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 9300 KB Output is correct
6 Correct 5 ms 7124 KB Output is correct
7 Correct 13 ms 17364 KB Output is correct
8 Correct 5 ms 7380 KB Output is correct
9 Correct 16 ms 17604 KB Output is correct
10 Correct 35 ms 30460 KB Output is correct
11 Correct 1 ms 3028 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 7 ms 9812 KB Output is correct
14 Correct 16 ms 20692 KB Output is correct
15 Correct 7 ms 10108 KB Output is correct
16 Correct 17 ms 21008 KB Output is correct
17 Correct 13 ms 18260 KB Output is correct
18 Correct 27 ms 31180 KB Output is correct
19 Correct 2 ms 3520 KB Output is correct
20 Correct 1 ms 1748 KB Output is correct
21 Correct 7 ms 10324 KB Output is correct
22 Correct 12 ms 13012 KB Output is correct
23 Correct 10 ms 10584 KB Output is correct
24 Correct 20 ms 21696 KB Output is correct
25 Correct 33 ms 35396 KB Output is correct
26 Correct 30 ms 31948 KB Output is correct
27 Correct 3 ms 3924 KB Output is correct
28 Correct 10 ms 13304 KB Output is correct
29 Correct 15 ms 4308 KB Output is correct
30 Correct 21 ms 13532 KB Output is correct
31 Correct 69 ms 25536 KB Output is correct
32 Correct 42 ms 22360 KB Output is correct
33 Correct 87 ms 36308 KB Output is correct
34 Correct 13 ms 6484 KB Output is correct
35 Correct 5 ms 4436 KB Output is correct
36 Correct 42 ms 6840 KB Output is correct
37 Correct 166 ms 49312 KB Output is correct
38 Correct 1401 ms 268244 KB Output is correct
39 Correct 158 ms 26772 KB Output is correct
40 Correct 555 ms 214564 KB Output is correct
41 Correct 1553 ms 338468 KB Output is correct
42 Correct 314 ms 54228 KB Output is correct
43 Correct 267 ms 110656 KB Output is correct
44 Correct 247 ms 110676 KB Output is correct