oj.uz

Submission #1102934

# Submission time Handle Problem Language Result Execution time Memory
1102934 2024-10-19T09:04:39 Z icebear Hotspot (NOI17_hotspot) C++17
38 / 100
 9 ms 74320 KB 
// ~~ icebear & at~~
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5000 + 5;
int numNode, numEdge, numQuery;
vector<int> G[N];
int dist[N][N], ways[N][N];
bool computed[N];
queue<int> Q;
int a[N], b[N];

void BFS(int x) {
    memset(dist[x], 0x3f, sizeof dist[x]);
    dist[x][x] = 0;
    ways[x][x] = 1;
    Q.push(x);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (int v : G[u])
            if (dist[x][v] > dist[x][u] + 1) {
                dist[x][v] = dist[x][u] + 1;
                ways[x][v] = ways[x][u];
                Q.push(v);
            } else if (dist[x][v] == dist[x][u] + 1)
                ways[x][v] = ways[x][u] + 1;
    }
}

bool isLarger(array<int, 3> &x, array<int, 3> &y) {
    return 1ll * x[0] * y[1] > 1ll * x[1] * y[0];
}

signed main(){
    // freopen("TRAINCENTRE.inp", "r", stdin);
    // freopen("TRAINCENTRE.out", "w", stdout);
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    cin >> numNode >> numEdge;
    for(int i = 0; i < numEdge; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    cin >> numQuery;
    for(int i = 0; i < numQuery; i++) {
        cin >> a[i] >> b[i];
        if (!computed[a[i]]) {
            BFS(a[i]);
            computed[a[i]] = true;
        }
        if (!computed[b[i]]) {
            BFS(b[i]);
            computed[b[i]] = true;
        }
    }

    array<int, 3> ans = {0, 1, 0};
    for(int w = 0; w < numNode; w++) {
        int fixedPath = 0, totalPath = 0;
        for(int i = 0; i < numQuery; i++) {
            if (dist[a[i]][w] + dist[b[i]][w] == dist[a[i]][b[i]]) 
                fixedPath += ways[a[i]][w] * ways[b[i]][w];
            totalPath += ways[a[i]][b[i]];
        }

        int g = __gcd(fixedPath, totalPath);
        array<int, 3> tmp = {fixedPath / g, totalPath / g, w};
        if (isLarger(tmp, ans)) ans = tmp;        
    }
    
    cout << ans[2];
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 1 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 1 ms 4688 KB Output is correct
12 Correct 1 ms 4688 KB Output is correct
13 Correct 1 ms 4860 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 1 ms 8784 KB Output is correct
8 Correct 4 ms 29316 KB Output is correct
9 Correct 8 ms 51792 KB Output is correct
10 Correct 7 ms 47696 KB Output is correct
11 Correct 9 ms 68340 KB Output is correct
12 Correct 2 ms 12880 KB Output is correct
13 Correct 2 ms 6736 KB Output is correct
14 Correct 6 ms 31312 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 1 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 1 ms 4688 KB Output is correct
12 Correct 1 ms 4688 KB Output is correct
13 Correct 1 ms 4860 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 29316 KB Output is correct
16 Correct 8 ms 51792 KB Output is correct
17 Correct 7 ms 47696 KB Output is correct
18 Correct 9 ms 68340 KB Output is correct
19 Correct 2 ms 12880 KB Output is correct
20 Correct 2 ms 6736 KB Output is correct
21 Correct 6 ms 31312 KB Output is correct
22 Correct 5 ms 35576 KB Output is correct
23 Correct 4 ms 31312 KB Output is correct
24 Correct 6 ms 49744 KB Output is correct
25 Correct 9 ms 74320 KB Output is correct
26 Correct 9 ms 68324 KB Output is correct
27 Correct 3 ms 15100 KB Output is correct
28 Correct 6 ms 37456 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 1 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 1 ms 4688 KB Output is correct
12 Correct 1 ms 4688 KB Output is correct
13 Correct 1 ms 4860 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 12880 KB Output is correct
16 Correct 3 ms 8784 KB Output is correct
17 Correct 8 ms 52048 KB Output is correct
18 Incorrect 6 ms 49860 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 1 ms 4688 KB Output is correct
5 Correct 2 ms 8784 KB Output is correct
6 Correct 3 ms 10832 KB Output is correct
7 Correct 1 ms 8784 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 8784 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 1 ms 4688 KB Output is correct
12 Correct 1 ms 4688 KB Output is correct
13 Correct 1 ms 4860 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 4 ms 29316 KB Output is correct
16 Correct 8 ms 51792 KB Output is correct
17 Correct 7 ms 47696 KB Output is correct
18 Correct 9 ms 68340 KB Output is correct
19 Correct 2 ms 12880 KB Output is correct
20 Correct 2 ms 6736 KB Output is correct
21 Correct 6 ms 31312 KB Output is correct
22 Correct 5 ms 35576 KB Output is correct
23 Correct 4 ms 31312 KB Output is correct
24 Correct 6 ms 49744 KB Output is correct
25 Correct 9 ms 74320 KB Output is correct
26 Correct 9 ms 68324 KB Output is correct
27 Correct 3 ms 15100 KB Output is correct
28 Correct 6 ms 37456 KB Output is correct
29 Correct 4 ms 12880 KB Output is correct
30 Correct 3 ms 8784 KB Output is correct
31 Correct 8 ms 52048 KB Output is correct
32 Incorrect 6 ms 49860 KB Output isn't correct
33 Halted 0 ms 0 KB -