oj.uz

Submission #1055713

# Submission time Handle Problem Language Result Execution time Memory
1055713 2024-08-13T04:17:58 Z 변재우(#11070) Treasure Hunt (CCO24_day1problem1) C++17
5 / 25
 4000 ms 198892 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=1000010, INF=1e18;
int N, M, A[Nmax], D[2*Nmax];
vector<pair<int, int>> adj[2*Nmax];
priority_queue<pair<int, int>> PQ;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=N; i++) cin>>A[i], adj[N+i].push_back({i, -A[i]});
    for(int i=1; i<=M; i++) {
        int u, v, w; cin>>u>>v>>w;
        adj[u].push_back({v, w}), adj[v].push_back({u, w});
    }
    fill(D+1, D+N+1, INF);
    for(int i=N+1; i<=2*N; i++) PQ.push({0, i});
    while(!PQ.empty()) {
        int curr=PQ.top().second, dist=-PQ.top().first; PQ.pop();
        if(D[curr]!=dist) continue;
        for(auto [next, w]:adj[curr]) if(D[next]>D[curr]+w) D[next]=D[curr]+w, PQ.push({-D[next], next});
    }
    for(int i=1; i<=N; i++) cout<<-D[i]<<"\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47704 KB Output is correct
2 Correct 10 ms 47708 KB Output is correct
3 Correct 12 ms 47708 KB Output is correct
4 Correct 13 ms 47964 KB Output is correct
5 Correct 8 ms 47196 KB Output is correct
6 Correct 8 ms 47232 KB Output is correct
7 Correct 8 ms 47432 KB Output is correct
8 Correct 10 ms 47708 KB Output is correct
9 Correct 12 ms 47708 KB Output is correct
10 Correct 10 ms 47708 KB Output is correct
11 Correct 8 ms 47448 KB Output is correct
12 Correct 9 ms 47708 KB Output is correct
13 Correct 8 ms 47196 KB Output is correct
14 Correct 8 ms 47196 KB Output is correct

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3620 ms 189576 KB Output is correct
2 Correct 3651 ms 198892 KB Output is correct
3 Correct 3462 ms 172020 KB Output is correct
4 Correct 2948 ms 173928 KB Output is correct
5 Execution timed out 4080 ms 160224 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1104 ms 180892 KB Output is correct
2 Correct 1208 ms 178032 KB Output is correct
3 Correct 1122 ms 180892 KB Output is correct
4 Correct 1122 ms 180896 KB Output is correct
5 Correct 9 ms 47196 KB Output is correct
6 Correct 9 ms 47196 KB Output is correct
7 Correct 3717 ms 173740 KB Output is correct
8 Execution timed out 4045 ms 164540 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47704 KB Output is correct
2 Correct 10 ms 47708 KB Output is correct
3 Correct 12 ms 47708 KB Output is correct
4 Correct 13 ms 47964 KB Output is correct
5 Correct 8 ms 47196 KB Output is correct
6 Correct 8 ms 47232 KB Output is correct
7 Correct 8 ms 47432 KB Output is correct
8 Correct 10 ms 47708 KB Output is correct
9 Correct 12 ms 47708 KB Output is correct
10 Correct 10 ms 47708 KB Output is correct
11 Correct 8 ms 47448 KB Output is correct
12 Correct 9 ms 47708 KB Output is correct
13 Correct 8 ms 47196 KB Output is correct
14 Correct 8 ms 47196 KB Output is correct
15 Correct 3620 ms 189576 KB Output is correct
16 Correct 3651 ms 198892 KB Output is correct
17 Correct 3462 ms 172020 KB Output is correct
18 Correct 2948 ms 173928 KB Output is correct
19 Execution timed out 4080 ms 160224 KB Time limit exceeded
20 Halted 0 ms 0 KB -