oj.uz

Submission #949089

# Submission time Handle Problem Language Result Execution time Memory
949089 2024-03-19T00:43:23 Z okkoo Sightseeing (NOI14_sightseeing) C++17
25 / 25
 1746 ms 196292 KB 
#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.0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16216 KB Output is correct
2 Correct 7 ms 15960 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18900 KB Output is correct
2 Correct 29 ms 18592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 124508 KB Output is correct
2 Correct 1746 ms 196292 KB Output is correct