oj.uz

Submission #170350

# Submission time Handle Problem Language Result Execution time Memory
170350 2019-12-24T20:24:15 Z ngmh Sightseeing (NOI14_sightseeing) C++11
15 / 25
 3500 ms 218580 KB 
#include <bits/stdc++.h>
using namespace std;

typedef  pair<int, int> pi;

int v, e, q, a, b, w, maxi[500001];
vector<pi> adjlist[500001];
priority_queue<pi> pq;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    memset(maxi, -1, sizeof(maxi));
    cin >> v >> e >> q;
    for(int i = 0; i < e; i++){
        cin >> a >> b >> w;
        adjlist[a].push_back(pi(b, w));
        adjlist[b].push_back(pi(a, w));
    }
    maxi[1] = INT_MAX;
    pq.push(pi(INT_MAX, 1));
    while(!pq.empty()){
        pi f = pq.top(); pq.pop();
        for(vector<pi>::iterator it = adjlist[f.second].begin(); it != adjlist[f.second].end(); it++){
            if(maxi[(*it).first] < min(f.first, (*it).second)){
                maxi[(*it).first] = min(f.first, (*it).second);
                pq.push(pi(maxi[(*it).first], (*it).first));
            }
        }
    }
    for(int i = 0; i < q; i++){
        cin >> a;
        cout << maxi[a] << "\n";
    }
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 17016 KB Output is correct
2 Correct 47 ms 16444 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3406 ms 164676 KB Output is correct
2 Execution timed out 3606 ms 218580 KB Time limit exceeded