oj.uz

Submission #334471

# Submission time Handle Problem Language Result Execution time Memory
334471 2020-12-09T07:50:48 Z ncduy0303 Hotspot (NOI17_hotspot) C++17
100 / 100
 827 ms 250988 KB 
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 5e3 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

int n, m, k;
vector<int> adj[MAX_N];
ll dist[MAX_N][MAX_N], cnt[MAX_N][MAX_N];
double p[MAX_N];

void bfs(int s) {
	queue<ar<int,2>> q;
	q.push({0, s});
	dist[s][s] = 0; cnt[s][s] = 1;
	while (!q.empty()){
		auto [d, u] = q.front(); q.pop();
		if (d > dist[s][u]) continue;
		for (int v : adj[u]) {
			if (dist[s][v] > dist[s][u] + 1) { 
				dist[s][v] = dist[s][u] + 1;
                cnt[s][v] = cnt[s][u];
				q.push({dist[s][v], v});
			}
			else if (dist[s][v] == dist[s][u] + 1) {
                cnt[s][v] += cnt[s][u];
            }
		}
	}
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(dist, 0x3f, sizeof dist);
    cin >> k;
    while (k--) {
        int u, v; cin >> u >> v;
        if (dist[u][u] > 0) bfs(u);
        if (dist[v][v] > 0) bfs(v);
        for (int i = 0; i < n; i++) {
            if (dist[u][v] == dist[u][i] + dist[v][i]) {
                p[i] += (double)(cnt[u][i] * cnt[v][i]) / cnt[u][v];
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (p[i] > p[ans]) {
            ans = i;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Compilation message

hotspot.cpp: In function 'void bfs(int)':
hotspot.cpp:29:22: warning: narrowing conversion of 'dist[s][v]' from 'long long int' to 'int' [-Wnarrowing]
   29 |     q.push({dist[s][v], v});
      |             ~~~~~~~~~^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 196332 KB Output is correct
2 Correct 106 ms 196332 KB Output is correct
3 Correct 105 ms 196332 KB Output is correct
4 Correct 107 ms 196204 KB Output is correct
5 Correct 105 ms 196260 KB Output is correct
6 Correct 103 ms 196224 KB Output is correct
7 Correct 104 ms 196344 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 196332 KB Output is correct
2 Correct 106 ms 196332 KB Output is correct
3 Correct 105 ms 196332 KB Output is correct
4 Correct 107 ms 196204 KB Output is correct
5 Correct 105 ms 196260 KB Output is correct
6 Correct 103 ms 196224 KB Output is correct
7 Correct 104 ms 196344 KB Output is correct
8 Correct 104 ms 196204 KB Output is correct
9 Correct 108 ms 196332 KB Output is correct
10 Correct 106 ms 196460 KB Output is correct
11 Correct 104 ms 196204 KB Output is correct
12 Correct 104 ms 196204 KB Output is correct
13 Correct 105 ms 196204 KB Output is correct
14 Correct 115 ms 196332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 196332 KB Output is correct
2 Correct 106 ms 196332 KB Output is correct
3 Correct 105 ms 196332 KB Output is correct
4 Correct 107 ms 196204 KB Output is correct
5 Correct 105 ms 196260 KB Output is correct
6 Correct 103 ms 196224 KB Output is correct
7 Correct 104 ms 196344 KB Output is correct
8 Correct 107 ms 196844 KB Output is correct
9 Correct 105 ms 197100 KB Output is correct
10 Correct 107 ms 197228 KB Output is correct
11 Correct 111 ms 197868 KB Output is correct
12 Correct 105 ms 196716 KB Output is correct
13 Correct 104 ms 196460 KB Output is correct
14 Correct 108 ms 197612 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 196332 KB Output is correct
2 Correct 106 ms 196332 KB Output is correct
3 Correct 105 ms 196332 KB Output is correct
4 Correct 107 ms 196204 KB Output is correct
5 Correct 105 ms 196260 KB Output is correct
6 Correct 103 ms 196224 KB Output is correct
7 Correct 104 ms 196344 KB Output is correct
8 Correct 104 ms 196204 KB Output is correct
9 Correct 108 ms 196332 KB Output is correct
10 Correct 106 ms 196460 KB Output is correct
11 Correct 104 ms 196204 KB Output is correct
12 Correct 104 ms 196204 KB Output is correct
13 Correct 105 ms 196204 KB Output is correct
14 Correct 115 ms 196332 KB Output is correct
15 Correct 107 ms 196844 KB Output is correct
16 Correct 105 ms 197100 KB Output is correct
17 Correct 107 ms 197228 KB Output is correct
18 Correct 111 ms 197868 KB Output is correct
19 Correct 105 ms 196716 KB Output is correct
20 Correct 104 ms 196460 KB Output is correct
21 Correct 108 ms 197612 KB Output is correct
22 Correct 106 ms 196844 KB Output is correct
23 Correct 106 ms 196972 KB Output is correct
24 Correct 107 ms 197356 KB Output is correct
25 Correct 109 ms 197996 KB Output is correct
26 Correct 110 ms 198052 KB Output is correct
27 Correct 105 ms 196844 KB Output is correct
28 Correct 107 ms 197996 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 196332 KB Output is correct
2 Correct 106 ms 196332 KB Output is correct
3 Correct 105 ms 196332 KB Output is correct
4 Correct 107 ms 196204 KB Output is correct
5 Correct 105 ms 196260 KB Output is correct
6 Correct 103 ms 196224 KB Output is correct
7 Correct 104 ms 196344 KB Output is correct
8 Correct 104 ms 196204 KB Output is correct
9 Correct 108 ms 196332 KB Output is correct
10 Correct 106 ms 196460 KB Output is correct
11 Correct 104 ms 196204 KB Output is correct
12 Correct 104 ms 196204 KB Output is correct
13 Correct 105 ms 196204 KB Output is correct
14 Correct 115 ms 196332 KB Output is correct
15 Correct 107 ms 196460 KB Output is correct
16 Correct 111 ms 196332 KB Output is correct
17 Correct 108 ms 196880 KB Output is correct
18 Correct 106 ms 196716 KB Output is correct
19 Correct 109 ms 196844 KB Output is correct
20 Correct 107 ms 196416 KB Output is correct
21 Correct 105 ms 196332 KB Output is correct

Subtask #6
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 196332 KB Output is correct
2 Correct 106 ms 196332 KB Output is correct
3 Correct 105 ms 196332 KB Output is correct
4 Correct 107 ms 196204 KB Output is correct
5 Correct 105 ms 196260 KB Output is correct
6 Correct 103 ms 196224 KB Output is correct
7 Correct 104 ms 196344 KB Output is correct
8 Correct 104 ms 196204 KB Output is correct
9 Correct 108 ms 196332 KB Output is correct
10 Correct 106 ms 196460 KB Output is correct
11 Correct 104 ms 196204 KB Output is correct
12 Correct 104 ms 196204 KB Output is correct
13 Correct 105 ms 196204 KB Output is correct
14 Correct 115 ms 196332 KB Output is correct
15 Correct 107 ms 196844 KB Output is correct
16 Correct 105 ms 197100 KB Output is correct
17 Correct 107 ms 197228 KB Output is correct
18 Correct 111 ms 197868 KB Output is correct
19 Correct 105 ms 196716 KB Output is correct
20 Correct 104 ms 196460 KB Output is correct
21 Correct 108 ms 197612 KB Output is correct
22 Correct 106 ms 196844 KB Output is correct
23 Correct 106 ms 196972 KB Output is correct
24 Correct 107 ms 197356 KB Output is correct
25 Correct 109 ms 197996 KB Output is correct
26 Correct 110 ms 198052 KB Output is correct
27 Correct 105 ms 196844 KB Output is correct
28 Correct 107 ms 197996 KB Output is correct
29 Correct 107 ms 196460 KB Output is correct
30 Correct 111 ms 196332 KB Output is correct
31 Correct 108 ms 196880 KB Output is correct
32 Correct 106 ms 196716 KB Output is correct
33 Correct 109 ms 196844 KB Output is correct
34 Correct 107 ms 196416 KB Output is correct
35 Correct 105 ms 196332 KB Output is correct
36 Correct 130 ms 197612 KB Output is correct
37 Correct 219 ms 207084 KB Output is correct
38 Correct 827 ms 250988 KB Output is correct
39 Correct 250 ms 204012 KB Output is correct
40 Correct 204 ms 209900 KB Output is correct
41 Correct 625 ms 242156 KB Output is correct
42 Correct 394 ms 212844 KB Output is correct
43 Correct 147 ms 202988 KB Output is correct
44 Correct 144 ms 202348 KB Output is correct