oj.uz

Submission #103437

# Submission time Handle Problem Language Result Execution time Memory
103437 2019-03-30T17:36:12 Z SecretAgent007 Sightseeing (NOI14_sightseeing) C++17
9 / 25
 3500 ms 237360 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

const int INF = 9223372036854775807;

vector< vector< pair< int, int > > > Graph;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int v, e, q;
    cin >> v >> e >> q;

    Graph.resize(v+1);

    for(int i = 0; i < e ; i++){
        int a, b, c;
        cin >> a >> b >> c;
        Graph[a].push_back(make_pair(b,c));
        Graph[b].push_back(make_pair(a,c));
    }

    vector< int > dist(v+1,-INF);

    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

    pq.push(make_pair(INF,1));

    while(!pq.empty()){

        pair<int, int> p = pq.top();

        int a = p.first;
        int b = p.second;

        pq.pop();

        if(dist[b] > a) continue;

        for(auto c : Graph[b]){
            if(dist[c.first] < min(a,c.second)){
                dist[c.first] = min(a,c.second);
                pq.push(make_pair(dist[c.first],c.first));
            }
        }
    }

    while(q--){
        int a;
        cin >> a;
        cout << dist[a] << endl;
    }

}
/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
3
4
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 640 KB Output is correct
2 Correct 9 ms 512 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3586 ms 5624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3539 ms 237360 KB Time limit exceeded
2 Halted 0 ms 0 KB -