oj.uz

Submission #124532

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

#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];
}

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);
    }
    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';
    }
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3504 ms 7856 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 3518 ms 93416 KB Time limit exceeded
2 Halted 0 ms 0 KB -