oj.uz

Submission #197514

# Submission time Handle Problem Language Result Execution time Memory
197514 2020-01-21T13:26:25 Z handlename Sightseeing (NOI14_sightseeing) C++17
15 / 25
 3500 ms 207656 KB 
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<pair<int,int> > adjList[500001]; // node, weight
    int v,e,q;
    cin>>v>>e>>q;
    for (int i=0;i<e;i++){
        int a,b,d;
        cin>>a>>b>>d;
        adjList[a].push_back(make_pair(b,d));
        adjList[b].push_back(make_pair(a,d));
    }
    priority_queue<pair<int,int> > pq; // distance, node
    int dist[500001];
    memset(dist,0,sizeof(dist));
    pq.push(make_pair(1000000000,1)); dist[1] = 1000000000;
    while (!pq.empty()){
        pair<int,int> c = pq.top();
        pq.pop();
        if (c.first != dist[c.second]) continue;
        for (auto i : adjList[c.second]){
            if (dist[i.first] < min(c.first,i.second)){
                dist[i.first] = min(c.first,i.second);
                pq.push(make_pair(dist[i.first], i.first));
            }
        }
    }
    for (int i=0;i<q;i++){
        int x;
        cin>>x;
        cout<<dist[x]<<'\n';
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14200 KB Output is correct
2 Correct 15 ms 14072 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14328 KB Output is correct
2 Correct 15 ms 14072 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16956 KB Output is correct
2 Correct 47 ms 16424 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3289 ms 164500 KB Output is correct
2 Execution timed out 3576 ms 207656 KB Time limit exceeded