Submission #124532

#	Time	Username	Problem	Language	Result	Execution time	Memory
124532		AdOjis485	Sightseeing (NOI14_sightseeing)	C++17	9 / 25	3518 ms	93416 KiB

sightseeing

//
//  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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 10