Submission #949089

#	Time	Username	Problem	Language	Result	Execution time	Memory
949089		okkoo	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	1746 ms	196292 KiB

sightseeing

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int mxn = 5e5;
vector<vector<pair<int, int> > > adj(mxn+1, vector<pair<int, int> >());
vector<array<int, 3> > edges;
vector<int> par(mxn+1);
vector<int> dp(mxn+1, 1e9);

bool compare(array<int, 3> a, array<int, 3> b){
    return a[2] > b[2];
}

int find(int node){
    if(par[node]==node) return node;
    par[node] = find(par[node]);
    return par[node];
}

bool unite(int u, int v){
    u = find(u), v = find(v);
    if(u==v) return 0;
    par[v] = u;
    return 1;
}

void dfs(int node, int par){
    for(pair<int, int> to: adj[node]){
        if(to.first != par){
            dp[to.first] = min(dp[node], to.second);
            dfs(to.first, node);
        }
    }
    return;
}

int main(){
    fastIO;
    int n, m, q;
    cin >> n >> m >> q;
    array<int, 3> edge;
    while(m--){
        cin >> edge[0] >> edge[1] >> edge[2];
        edges.push_back(edge);
    }
    sort(edges.begin(), edges.end(), compare);
    for(int i=1; i<=n; i++) par[i] = i;
    for(array<int, 3> edge: edges){
        int u = edge[0], v = edge[1], w = edge[2];
        if(unite(u, v)){
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }
    dfs(1, 0);
    while(q--){
        int node;
        cin >> node;
        cout << dp[node] << '\n';
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10