Submission #1170589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170589		Bzslayed	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1401 ms	98876 KiB

sightseeing

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define ll long long
#define ull unsigned long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define coutpair(p) cout << p.first << " " << p.second << "|"

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

pair<int, pii> edges[5000005];
int par[5000005];

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

bool same(int x, int y) {
    return find(x) == find(y);
}

void join(int x, int y) {
    x = find(x);
    y = find(y);
    par[x] = y;
}

vector<pii> adj[500005];
ll dist[500005];

void dfs(int cur, int par){
    for (pii child : adj[cur]){
        if (child.first != par){
            dist[child.first] = min(dist[cur], (ll)child.second);
            dfs(child.first, cur);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);

    int v, e, q; cin >> v >> e >> q;
    for (int i=1; i<=v; i++) par[i] = i;
    for (int i=0; i<e; i++) cin >> edges[i].second.first >> edges[i].second.second >> edges[i].first;

    sort(edges, edges+e, greater<pair<int, pii>>());

    for (int i=0; i<e; i++){
        int fi = edges[i].second.first, se = edges[i].second.second, weight = edges[i].first;
        if (!same(fi, se)){
            join(fi, se);
            adj[fi].push_back({se, weight});
            adj[se].push_back({fi, weight});
        }
    }
    dist[1] = LLONG_MAX;
    dfs(1, 1);

    for (int i=0; i<q; i++){
        int x; cin >> x;
        cout << dist[x] << "\n";
    }

    return 0;
}

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