oj.uz

Submission #124545

# Submission time Handle Problem Language Result Execution time Memory
124545 2019-07-03T13:41:17 Z AdOjis485 Sightseeing (NOI14_sightseeing) C++14
15 / 25
 3500 ms 92956 KB 
//
//  main.cpp
//  sightseeing
//
//  Created by AdOjis485 on 03.07.19.
//  Copyright © 2019 AdOjis485. All rights reserved.
//

#include <limits>
#include <iostream>
#include <vector>
#include <queue>
#define int int64_t
using namespace std;
/*
bool bfs(int x, int m, vector<vector<pair<int, int>>> adi){
    queue<int> q;
    q.push(0);
    vector<bool> vis(adi.size(), false);
    while(q.size() > 0){
        int cur = q.front();
        q.pop();
        if(!vis[cur]){
            vis[cur] = true;
            for(pair<int, int> next : adi[cur]){
                if(!vis[next.first] && next.second >= m){
                    q.push(next.first);
                }
            }
        }
    }
    return vis[x];
}
*/

vector<int> dijkstra(vector<vector<pair<int, int>>>& adi){
    priority_queue<pair<int, int>> pq;
    pq.push({numeric_limits<int>::max(), 0});
    vector<int> vis(adi.size(), -1);
    while(pq.size() > 0){
        int cur = pq.top().second;
        int cq = pq.top().first;
        pq.pop();
        if(vis[cur] == -1 || vis[cur] < cq){
            vis[cur] = cq;
            for(pair<int, int> next : adi[cur]){
                if(vis[next.first] < cq){
                    pq.push({min(cq, next.second), next.first});
                }
            }
        }
    }
    return vis;
}

signed main() {
    int v, e, q;
    cin >> v >> e >> q;
    vector<vector<pair<int, int>>> adi(v);
    int maxq = 0;
    for(int i = 0; i < e; i ++){
        int v1, v2, qu;
        cin >> v1 >> v2 >> qu;
        v1 --;
        v2 --;
        adi[v1].push_back({v2, qu});
        adi[v2].push_back({v1, qu});
        maxq = max(maxq, qu);
    }
    vector<int> vis = dijkstra(adi);
    for(int i = 0; i < q; i ++){
        int x;
        cin >> x;
        x --;
        /*
        int mi = 0;
        int ma = maxq + 1;
        while(mi < ma - 1){
            int m = (mi + ma) / 2;
            if(bfs(x, m, adi)){
                mi = m;
            }
            else{
                ma = m;
            }
        }
        cout << mi << '\n';
         */
        cout << vis[x] << '\n';
    }
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 628 KB Output is correct
2 Correct 4 ms 504 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 5236 KB Output is correct
2 Correct 105 ms 4600 KB Output is correct

Subtask #4
0 / 10.0

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