oj.uz

Submission #1113224

# Submission time Handle Problem Language Result Execution time Memory
1113224 2024-11-16T05:06:13 Z votranngocvy Sightseeing (NOI14_sightseeing) C++14
25 / 25
 1835 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
const int N = 5e5 + 5;
const int inf = 1e18;
vector<pii>adj[N];
vector<piii>edge;
int par[N],sz[N],f[N];

void make_set(int v) {
    par[v] = v;
    sz[v] = 1;
}

int find_set(int v) {
    if (v == par[v]) return v;
    int p = find_set(par[v]);
    par[v] = p;
    return p;
}

bool union_sets(int a,int b) {
    a = find_set(a),b = find_set(b);
    if (a == b) return 0;
    if (sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b];
    par[b] = a;
    return 1;
}

void dfs(int u,int p) {
    for (auto x: adj[u]) {
        int v = x.fi,w = x.se;
        if (v == p) continue;
        f[v] = min(f[u],w);
        dfs(v,u);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,e,q;
    cin >> n >> e >> q;
    for (int i = 1; i <= e; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        edge.push_back({w,{u,v}});
    }
    sort(edge.begin(),edge.end(),greater<piii>());
    for (int i = 1; i <= n; i++) make_set(i);
    for (auto x: edge) {
        int u = x.se.fi,v = x.se.se,w = x.fi;
        if (union_sets(u,v)) {
            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }
    }
    f[1] = inf;
    dfs(1,-1);
    while (q--) {
        int u;
        cin >> u;
        cout << f[u] << "\n";
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12112 KB Output is correct
2 Correct 9 ms 12164 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12384 KB Output is correct
2 Correct 9 ms 12112 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16580 KB Output is correct
2 Correct 29 ms 16200 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1275 ms 111572 KB Output is correct
2 Correct 1835 ms 262144 KB Output is correct